dp

[백준] 11659. 구간 합 구하기 4 - 파이썬

https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 풀이 1 Brute-Force로 풀어봤으나 시간초과 N, M = map(int, input().split()) nums = list(map(int, input().split())) totals = [] for _ in range(M): total = 0 i, j = map(int, input().split()) for k in range(i-1, j): total += nu..

[백준] 1463. 1로 만들기 - 파이썬

https://www.acmicpc.net/problem/1463 풀이 1 정말 단순하게 생각하면, "당연히 3으로 나누는게 가장 빨리 숫자를 줄일 수 있고, 그 다음이 2로 나누는 거고, 그 다음에 1을 빼는 것을 택하는 게 제일 유리한 거 아닌가?" 라고 생각할 수 있다. (약간의 Greedy 느낌!) 그러나, 10의 Input 예시만 생각해 봐도, 위와 같은 알고리즘으로는 10은 2로 나눠지므로, 10/2 = 5 5는 3, 2로 나눠지지 않으므로, 5-1=4 4는 2로 나눠지므로, 4/2 = 2 2는 2로 나눠지므로, 2/2 = 1 로 4번의 연산만에 1이 된다. 그러나, 첫 번째 단계에서 1을 빼는 것을 택한다면, 10 - 1 = 9 9 / 3 = 3 3 / 3 = 1 로 3번의 연산만에 1을 만..

[백준] 1003. 피보나치 함수 - 파이썬

https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 풀이 문제 이름부터 대놓고 피보나치 함수인데.. DP 써야겠죠? Top-Down 방식(재귀)로 구현함. 일반적으로 DP의 예시로 많이 나오는 게 피보나치 함수인데, 그거 생각하면서 풀었던 것 같다. 다만 원하는 결과값이 좀 다르므로, 잘 처리해주면 될 듯. dp = dict() test = [int(input()) for _ in range(int(input()))] def fib(n): if dp.get(n, -1) != -1: return dp[n] elif n == 0: return [1..

[백준] 2281. 데스노트 - 파이썬

https://www.acmicpc.net/problem/2281 풀이 DP (Dynamic Programming) 문제. 나는 기본적으로 DP는 bottom-up 방식으로 푸는 것을 선호하고, 풀이도 bottom-up 방식으로 먼저 생각해내곤 하는데, 이 문제는 잘 생각이 나지 않아 시도하다 다시 top-down 방식으로 선회한 문제. top-down 방식으로 푸는 것이 훨씬 구현하기 수월했다. 먼저 기저 상태를 0으로 설정하고, memoization을 활용해 이미 계산된 dp[index]가 존재하면 (maxNum으로 초기화했으므로, maxNum보다 작으면 값이 담긴 것) 그 값을 return. dp[index]는 index+1번째의 이름을 '새로운 줄' 에 작성할 때, 남은 공간들의 제..