흙금이네 블로그

아이디어 A의 최솟값을 갱신하면서 차이의 최댓값을 저장해 나간다. 풀이 #1 (Python) def solution(): N = int(input()) A = tuple(map(int, input().split())) res = '0' min_val = A[0] max_d = 0 for i in range(1, N): if A[i] max_d: max_d = A[i]-min_val res += f' {max_d}' print(res) solution() 풀이 #2 (JavaScript) const fs = require('fs'); const input = fs.readFileSync('/dev/stdin').toString(..

아이디어 DP로 현재 수까지의 곱과 현재 수를 비교하여 갱신하면서 곱의 최댓값을 저장해 나간다. 풀이 #1 (Python) 이 문제가 그리디인지 DP인지 고민했는데, 이전 값이 현재 선택에 영향을 미치기 때문에 DP라고 이해했다. import sys input = sys.stdin.readline def solution(): N = int(input()) temp = 1 res = 0 for i in range(N): number = float(input()) temp *= number if number > temp: temp = number if temp > res: res = temp print(f'{res:.3f}') solution() 아래 테스트 케이스 수들의 곱은 1185.9705로, 소수점 ..

아이디어 DP로 파스칼 삼각형의 수들을 구하고 입력으로 주어지는 삼각형 내부에 있는 수의 합을 구한다. 풀이 #1 (Python) def solution(): R, C, W = map(int, input().split()) pt = [[0]*30 for _ in range(30)] pt[1][1] = 1 for i in range(2, 30): for j in range(1, i+1): pt[i][j] = pt[i-1][j-1]+pt[i-1][j] res = 0 for d in range(W): for j in range(C, C+d+1): res += pt[R+d][j] print(res) solution() 풀이 #2 (JavaScript) const fs = require('fs'); const i..

아이디어 DP로 수열의 값을 구해 나간다. 풀이 #1 (Python) def solution(): n = int(input()) t = [0]*(n+1) t[0] = 1 for i in range(1, n+1): for j in range(i//2): t[i] += t[j]*t[i-j-1] t[i] *= 2 if i%2: t[i] += t[i//2]**2 print(t[-1]) solution() 풀이 #2 (JavaScript) const fs = require('fs'); const input = fs.readFileSync('/dev/stdin').toString().split('\n'); function solution() { const n = Number(input[0]); let t = Arr..

아이디어 DP로 완전순열을 구한다. 풀이 #1 (Python) 점화식을 구하기 위해 임의로 학생과 기숙사에 번호를 매기고, 1번 학생이 K번 기숙사에 배정되는 경우를 고려한다. K번 학생이 1번 기숙사에 배정되는 경우의 수는 1번 학생과 K번 학생을 제외하고 학생 수가 N-2인 경우의 수와 같다. K번 학생이 1번 기숙사에 배정되지 않는 경우의 수는 1번 학생을 제외하고 학생 수가 N-1인 경우의 수와 같다. K는 1을 제외한 N-1개의 수가 가능하므로 두 경우의 수를 더하여 N-1만큼 곱하면 학생 수가 N인 경우의 수를 구할 수 있다. import sys input = sys.stdin.readline def solution(): T = int(input()) dp = [0]*21 dp[2] = 1 f..

아이디어 DP로 사탕 가격의 합에 대한 경우의 수를 구해 나가고, 에라토스테네스의 체로 가격 합이 소수인지 확인한다. 풀이 #1 (Python) dp[i]는 가격 합이 i인 사탕을 사는 방법의 수를 나타낸다. import sys input = sys.stdin.readline def solution(): N = int(input()) candies = dict() total = 0 zero = 1 for _ in range(N): price = int(input()) if price: candies[price] = candies.get(price, 0)+1 total += price else: zero += 1 P = [1]*(total+2) P[0] = P[1] = 0 for i in range(2, ..

아이디어 동적 계획법으로 개근상을 받을 수 있는 출결 정보의 개수를 더해 나간다. 풀이 dp[i][j][k]에서 i는 일수의 인덱스, j는 지각 횟수, k는 연속 결석 횟수를 나타낸다. def solution(): N = int(input()) p = 1000000 dp = [[[0]*3 for _ in range(2)] for _ in range(N)] dp[0][0][0] = dp[0][1][0] = dp[0][0][1] = 1 for i in range(N-1): dp[i+1][0][0] = (dp[i][0][0]+dp[i][0][1]+dp[i][0][2])%p dp[i+1][0][1] = dp[i][0][0] dp[i+1][0][2] = dp[i][0][1] dp[i+1][1][0] = (dp[i..

아이디어 동적 계획법으로 부분 서열들 중 KOI 유전자의 최대 길이를 저장해 나간다. 풀이 dp[i][j]는 인덱스 i부터 j까지의 DNA 서열에서 가장 긴 KOI 유전자 길이를 저장한다. def solution(): DNA = input() N = len(DNA) dp = [[0]*N for _ in range(N)] for j in range(1, N): for i in range(j-1, -1, -1): if (DNA[i] == 'a' and DNA[j] == 't') or (DNA[i] == 'g' and DNA[j] == 'c'): dp[i][j] = dp[i+1][j-1]+2 for k in range(i, j): if dp[i][k]+dp[k+1][j] > dp[i][j]: dp[i][j] ..

아이디어 동적 계획법과 DFS로 순열에서 올바른 출근 기록이 있는지 확인한 후 해당 순열을 만든다. 풀이 dp[a][b][c][p2][p1]에서 a, b, c는 각각 남은 출근 횟수, p1은 전날 출근자, p2는 전전날 출근자를 나타낸다. def solution(): def dfs(a, b, c, p2, p1): if dp[a][b][c][p2][p1]: return dp[a][b][c][p2][p1] = 1 if a > 0: dfs(a-1, b, c, p1, 0) if b > 0 and p1 != 1: dfs(a, b-1, c, p1, 1) if c > 0 and p1 != 2 and p2 != 2: dfs(a, b, c-1, p1, 2) S = input() N = len(S) B, C = S.cou..

아이디어 동적 계획법으로 각 차례에서 발 위치에 따른 힘의 최솟값을 구해 나간다. 풀이 power = [ (0, 2, 2, 2, 2), (0, 1, 3, 4, 3), (0, 3, 1, 3, 4), (0, 4, 3, 1, 3), (0, 3, 4, 3, 1), ] def solution(): numbers = tuple(map(int, input().split())) queue = [((0, 0), 0)] for number in numbers: pos = dict() for (left, right), p in queue: if p+power[left][number] < pos.get((number, right), 400000): pos[(number, right)] = p+power[left][number..