DynamicProgramming
-
[백준] 1932번 정수 삼각형 (by Python)Programming/Algorithm 2021. 2. 21. 18:32
문제 점화식을 찾는 것은 사실 무척 쉬웠지만 인덱스를 헷갈려 시간을 낭비했다. 언제나 느끼지만 문제를 잘 푸는 것은 논리력뿐만 아니라 실수를 하지 않는 것도 포함되는 것 같다. 풀이 import sys input = sys.stdin.readline n = int(input()) arr = [] dp = [[0] * (i + 1) for i in range(n)] for _ in range(n): arr.append(list(map(int, input().strip().split()))) dp[0][0] = arr[0][0] for i in range(1, n): for j in range(i + 1): if j == 0: dp[i][j] = dp[i - 1][0] + arr[i][j] elif j ==..
-
[백준] 2156번 포도주 시식 (by Python)Programming/Algorithm 2021. 2. 16. 13:41
문제 짜고 보니 몇 줄 안됐지만 하루종일 머리 싸매다가 다른 분의 해설을 보고 나서야 해답을 찾은 문제. 풀이 import sys input = sys.stdin.readline n = int(input()) arr = [] ans = [0 for _ in range(n)] for _ in range(n): arr.append(int(input())) ans[0] = arr[0] if n > 1: ans[1] = arr[0] + arr[1] if n > 2: ans[2] = max(arr[0] + arr[1], arr[1] + arr[2], arr[0] + arr[2]) for i in range(3, n): ans[i] = max(ans[i - 1], ans[i - 2] + arr[i], ans[i -..
-
[백준] 9465번 스티커 (by Python)Programming/Algorithm 2021. 2. 14. 23:16
문제 제법 Dynamic Programming에 익숙해졌다고 생각했는데 점화식을 떠올리기가 힘들었던 문제. 메모이제이션 방법을 떠올렸지만 점화식의 형태를 구상하기가 힘들었다. 수열로 따졌을 때 새로 추가되는 column의 값들에 따라서 최댓값도 달라지기 때문에 그랬던 것 같다. 이 문제의 breakthrough는 크게 다음 2가지였던 것 같다. ① 새로운 값이 어떤 값이냐에 따라서 답이 달라진다면 다 대입해볼 것! ② 메모이제이션으로 해당 값까지의 최적 경로에 대한 축적을 한다는 것을 기억하고 무엇을 축적해야할지 생각할 것! 풀이 t = int(input()) for _ in range(t): n = int(input()) arr = [] ans = [[0] * n for _ in range(2)] fo..