Dp

백준 14501번 문제 바로가기 Bottom-Up 방식 문제는 이해했는데 ‘이걸 어떻게 구현하지’라는 생각에 문제를 해결하기까지 꼬박 이틀이 걸렸다. 예제들을 직접 손으로 그려보기도 하고, 문제를 다시 분석해보면서 해결책을 찾았다. Bottom-Up 방식이 그나마 직관적이고 이해하기 편해서 다음과 같이 구현했다. 0에서 n까지 index에 대해서 이중 max()로 값을 비교하고 최대 기댓값을 산출하는 알고리즘을 구현했다. # 입력 import sys n = int(sys.stdin.readline()) work = list(tuple(map(int, sys.stdin.readline().split())) for i in range(n)) dp = [0] * (n+1) # 처리 # bottom-up 방식 for i in range(n): if i+work[i][0] <= n: dp[i+work[i][0]] = max(dp[i+work[i][0]], max(dp[:i+1]) + work[i][1]) print(max(dp)) Top-Down 방식 아무리 고민해도 Top-Down 방식 구현이 어려워서 다른 블로그들을 참고했다. 예시 꾸준히 공부해나가면서 다른 접근으로도 풀어낼 수 있도록 실력을 키워야겠다. ...

백준 1904번 문제 바로가기 조합(combinations)을 이용한 풀이 (시간초과) # 입력 import sys import math n = int(sys.stdin.readline()) ans = 0 # 처리 for i in range(n//2 + 1): ans += math.comb((n-i), i) print(ans) # N=4 # 4C0 1111 # 3C1 0011, 1001, 1100 # 2C2 0000 dp 풀이 조합으로 풀었더니 시간초과 문제가 발생해서, dp 방식으로 풀어보기로 했다. (참 쉽지 않구만!) 하긴 0.75초의 시간제한이 걸려있는걸 보면 bruteforce는 아니겠구만! 생각이 들긴 하다. 그래서 생각한 것은 dp 방식으로 풀어보자! (길이가 n일 떄의 가짓수) = $ a_{n} $ 이라면, $ a_{n} = a_{n-1} + 2 * a_{n-2} $ 을 만족한다 (n-1에 1을 추가하는 경우) (n-2에 11또는 00을 추가하는 경우) ...

백준 2193번 문제 바로가기 재귀를 통한 풀이 (시간초과..) 재귀를 이용하여 풀어보려고 했건만, 시간초과로 실패했다. 시간제한 2초인데도 걸리다니 빡세구만… # 입력 import sys n = int(sys.stdin.readline()) count = 0 # 처리 def pinary(arr = [1]): if len(arr) == n: global count count += 1 return else: if arr[-1] == 1: pinary(arr + [0]) else: pinary(arr + [0]) pinary(arr + [1]) pinary() print(count) dp을 이용한 풀이 러닝타임을 줄이기 위해서 주어진 이친수의 규칙을 파악해보았다. (0으로 끝나는 길이가 n인 이친수의 갯수)를 $ a_{n} $ (1로 끝나는 길이가 n인 이친수의 갯수)를 $ b_{n} $ 이라고 두면 $ a_{n} = a_{n-1} + b_{n-1} $ $ b_{n} = a_{n-1} $ 의 식을 만족한다. $ a_{0} = 0, b_{0} = 1 $ 의 초항을 대입하여 점화식을 풀면 n길이의 이친수의 갯수를 쉽게 구할 수 있다. ...

백준 17626번 바로가기 나의 풀이 # 입력 import sys n = int(sys.stdin.readline().strip()) squares = [i**2 for i in range(1,int(n**0.5)+1)] queue = [n] count = 0 # 처리 - bfs 활용 while len(queue) > 0: count += 1 temp = set() for q in queue: for s in squares: if q < s: break temp.add(q-s) if 0 in queue: break queue = list(temp) print(count-1) 고수의 풀이 dp = [50001 for i in range(n + 1)] dp[0] = 0 for i in range(1, n + 1): for j in range(1, i + 1): val = j * j if val > i: break dp[i] = min(dp[i], dp[i - val] + 1) print(dp[n]) 출처 CODE REVIEW 처음에는 제곱수들을 역순으로 배열해서 차례대로 빼면 되겠지 생각했지만, 그게 최선의 수가 아니라는걸 깨달았다… bfs을 응용해서 n에서 0까지 top2bottom 방식으로 알고리즘을 구상했다. BFS(너비 우선 탐색) 방식이 층별로 내려가는 식이라 과정이 유사하다는 점에서 착안했다. dp로는 도저히 풀어내는 방법을 모르겠어서 다른 사람의 풀이를 참고했다. 짧고 깔끔하게 잘 짰구만…👍👍 min(dp[i], dp[i-val]+1) 발상이 쉽지 않다. 허허

백준 11726번 바로가기 나의 풀이 # 입력 import sys read = sys.stdin.readline arr = [1, 2, 3] + [0]*1000 # 처리 for i in range(n:=int(read().strip())): arr[i+2] = (arr[i+1] + arr[i]) % 10007 print(arr[n-1]) CODE REVIEW (1*2) 한 개 또는 (2*1) 위아래로 두 개 쌓는 방식을 택할 수 있어서, n을 1, 2의 합으로 나타내는 경우의 수를 구하는 문제로 바뀐다. 점화식은 $a_{n+2} = a_{n+1} + a_{n}$ n+1에 (1*2) 한 개 넣거나, n에 (2*1) 위아래로 두 개 넣는 경우의 합으로 계산할 수 있다. cf) 피보나치 수열과 동일.