DP
-
[백준] 17070번 파이프 옮기기 1 (by Python)Programming/Algorithm 2021. 4. 8. 22:52
문제 www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 풀이 처음에는 직관적으로 생각나는 대로 다음과 같이 BFS로 풀었다. import sys from collections import deque input = sys.stdin.readline n = int(input()) arr = [list(map(int, input().split())) for _ in range(n)] q = deque() q.append([(0, 0), (0..
-
[백준] 2293번 동전 1 (by Python)Programming/Algorithm 2021. 3. 31. 20:15
문제 https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 DP가 늘 그렇듯, 아이디어가 중요한 문제이다. n, k = map(int, input().split()) arr = sorted([int(input()) for _ in range(n)]) ans = [0 for i in range(k + 1)] ans[0] = 1 for i in range(1, k + 1): for j in arr: if i >= j: ans[i] += ans[i -..
-
[백준] 2225번 합분해 (by Python)Programming/Algorithm 2021. 2. 28. 17:34
문제 0 이상 N 이하의 정수 K개를 더해 N을 만든다고 할 때, K가 1이면 N이 어떤 수든 방법은 1가지이다. 이러한 리스트를 dp_k로 나타낸다고 하면 dp_1은 길이가 n인 [1, 1, 1, 1 ...] 의 모습을 하고 있을 것이다. 그리고 2 이상의 k에 대해서는 dp_k[i] = sum(dp[:i + 1])이다. 풀이 n, k = map(int, input().split()) dp = [1] * (n + 1) k -= 1 while k: next_dp = [1] * (n + 1) for i in range(1, n + 1): next_dp[i] = sum(dp[:i + 1]) dp = next_dp[:] k -= 1 print(dp[-1] % 1000000000)
-
[백준] 1699번 제곱수의 합 (by Python)Programming/Algorithm 2021. 2. 28. 17:19
문제 비슷한 문제인 1, 2, 3 더하기가 있지만 이 문제는 1, 2, 3이 아니라 n과 같거나 작은 모든 제곱수를 다 고려해야한다는 점에서 시간복잡도가 더 높은 문제이다. 그래서 Pypy3 환경에서만 성공할 수 있었다는 아쉬움이 있지만 이 문제에서 요구한 사고력은 내 풀이로도 충분하다고 생각해 더 이상의 최적화를 시도하진 않았다. 풀이 from math import sqrt n = int(input()) sq_num = [i ** 2 for i in range(1, int(sqrt(n) + 1))] dp = [1 if i in sq_num else i for i in range(n + 1)] for i in range(2, n + 1): for j in range(1, int(sqrt(i)) + 1):..
-
[백준] 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..
-
[백준] 14226번 이모티콘 (by Python)Programming/Algorithm 2021. 2. 7. 00:48
문제 처음에는 떠오르는대로 BFS로 풀었지만 코드를 짜는 와중에도 뭔가 문제를 다 파악하지 못한 풀이라는 생각이 들었고, 아니나 다를까 나보다 시간을 90% 정도 절약한 분들은 Dynamic Programming을 통해 푸신 분들이었다. 간결한 코드에 끌려 원리를 고민해봤지만 수학적인 증명은 스스로 해내지 못했다. 고민해보았고, 앞으로도 더 고민해보겠지만 지금은 더 다양한 테스트 케이스에서 해당 원리가 적용된다는 확신이 없으므로 이런 유형의 문제를 만났을 때는 확실한 풀이를 먼저 시도해볼 것 같다. 좀 느릴지라도, 스스로 납득되는 코드를 짜고 싶다. 첫 번째 풀이 (by BFS) from collections import deque s = int(input()) q = deque() next_q = de..