![]()
https://www.acmicpc.net/problem/2096 설명N은 1 이상 10만 이하로, 한 줄에는 3칸이 있고 각 칸에는 최대 9까지 올 수 있으므로, 최악의 경우의 합을 더해도 9 * 10만 = 90만으로 int의 최댓값보다 작다. 또한 메모리가 4MB인데, 4byte(int) * 3칸 * 10만 줄 = 1.2MB로, 입력받는 배열에 최댓값, 최솟값 + 기타 연산하면서 생기는 객체들까지 고려하면 메모리 초과가 날 것 같았다. 그래서 입력 배열은 따로 만들지 않고 최댓값 배열과 최솟값 배열만 만들되, 각각 2 * 3 배열을 만들어서 값을 재사용하기로 했다. 우선 N과 최댓값 배열 maxArr, 최솟값 배열 minArr을 선언해준다. 그리고 각 배열을 2*3으로 초기화해준다. i / j0..
https://www.acmicpc.net/problem/11048 설명전형적인 DP 문제이다. 문제에서는 (r+1, c), (r, c+1), (r+1, c+1)로 이동할 수 있다는 부분 때문에 현재 위치를 기준으로 다음 위치의 값을 어떻게 넣어줄지 생각하게 되는데, DP는 역으로 현재 위치의 값이 과거의 어느 위치로부터 영향받았는지로 생각하면 조금 더 수월하게 풀린다. 물론 그래도 DP는 너무 어렵다.,... 문제의 답이 N, M에 도착할 때 가장 많은 사탕을 가지고 있어야 하는 경우이고, 이동은 오른쪽, 아래, 오른쪽 아래 대각선 3방향으로 밖에 이동하지 못한다는 조건으로 생각해 보자. 두 번째 조건을 반대로 생각해보면, 현재 위치에 있으려면 그전에는 왼쪽, 위, 왼쪽 위 대각선 중 하나에 있어야..
![]()
https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 동적 계획법, 그중에 상향식(Tabulation)으로 풀었다. 처음에는 백트래킹으로 풀어봤는데 시간초과가 났다. 메모리가 4MB 밖에 안 되어서 dp는 아니겠다 싶었는데 dp로 푸는 거였다. 풀이에 사용하는 변수들과 입력이다. N, K는 각각 동전 개수와 만들어야 하는 금액이며, 동전을 받기 위해 리스트를 만들어 입력해주었고, 동적 계획법으로 푸므로 dp를 0부터 K를 범위로 하는 정수 배열로 선언..
https://www.acmicpc.net/problem/11051 11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net # 파이썬에서는 재귀 최대 한도의 디폴트가 1000이기 때문에 더 늘려주려면 다음의 코드가 필요 import sys sys.setrecursionlimit(10 ** 7) n, k = map(int, input().split()) MOD = 10007 cache = [[0] * 1001 for _ in range(1001)] # N, K는 1부터 1000까지 이므로 이중 배열 생성 # 이항계수 nCk를 bino(n, k) 라 하면, # bino(n, k) = bino..
https://www.acmicpc.net/problem/2748 2748번: 피보나치 수 2 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net n = int(input()) cache = [-1] * 91 # n이 최대 90이므로, 0~90까지 91개의 공간 필요. cache[0] = 0 # 피보나치 수의 F0은 0 cache[1] = 1 # 피보나치 수의 F1은 1 def fi_bottomup(n): # Tabulation, 순서 중요 for i in range(2, n + 1): # 0, 1은 미리..
https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net MOD = 1_000_000_000 # cache[n][d] = 길이가 n, 마지막 숫자가 d인 계단수 개수 cache = [[0] * 10 for _ in range(101)] # n은 1~100 이므로 101개를 만들고, d는 0~9까지니까 10개를 만든다. for d in range(1, 10): # cache[1][0] 은 0으로 시작하므로 문제 조건에 따라 0이다. cache[1][d] = 1 # 길이가 1이고 자릿수가 0이 아니면 초기값은 1이다. for N in range(2, 101): # 길이 ..
