DHistory

문제 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net 풀이 1. 1로 만들기의 응용으로 생각하여 1로 만들기의 뼈대를 활용하였다. 2. 최소값을 구하는 부분에서 어떤 값을 선택할 지가 주된 문제이다. 3. DP는 큰 문제를 작은 문제로 해결할 수 있기 때문에 연속된 참조하고 있다. 3-1. 10인 경우 9와 5중 1로 만들 수 있는 경우의 수 중 작은 값을 선택한다. 3-2. 이 때, 9는 다음으로 3을 참조하고 5는 4를 참조한다. 3-3. 이를 반복하여 최종 결과물은 10 -> 9 -> 3 -> 1이 등장하게 된다. 4. 해당 참조를 구하기 위한 값을 따로 저장했다. (answer) n = int(input())..

문제 1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net 풀이 1. Start(왼쪽 위)에서 주어진 거리만큼 오른쪽 or 아래로 이동할 수 있다. 2. Start를 기점으로 오른쪽으로 이동하는 경우와 아래로 이동하는 경우를 각 값(d)을 할당해준다. 2-1. 기준으로부터 오른쪽으로 이동하는 경우 2-2. 기준으로부터 아래쪽으로 이동하는 경우 2-3. 범위를 벗어난 경우 이동할 수 없다. 3. Goal에 도달하면 진행을 막는 종착점이기에 더 이상 진행하지 않는다. import sys n = int(sys..

문제 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 풀이 d[n][m]: 우리의 크기가 n일 때, m의 배치에 따라 사자를 배치를 경우의 수 1번째 경우 사자를 1번째 칸에 배치하는 경우 2번째 경우 사자를 2번째 칸에 배치하는 경우 3번째 경우 사자를 아예 배치하지 않는 경우 따라서, d[n][m]은 다음 사진과 같은 상황으로 배치할 수 있다. 1번째 경우 사자를 1번째 칸에 위치해있으므로, 직전에 배치할 때는 2번째 칸에 배치하거나 아예 배치하지 않을 수 있다. 2번째 경우 사자를 2번째 칸에 위치해있으므로, 직전에 배치할 때는 1번째 칸에 배치하거나 아예 배치하지 않을 수 있다. 3번째 경우 현재 사자를 배치하지 않았으므로, 직전에는 ..

문제 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 풀이 import sys n, m = map(int, sys.stdin.readline().rstrip().split()) numbers = [] for _ in range(n): data = list(map(int, sys.stdin.readline().rstrip().split())) numbers.append(data) coordinates = [] for _ in range(m): coordinate = li..

문제 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 풀이 import sys t = int(sys.stdin.readline().rstrip()) def solution(n, a, b): d = [[0, 0] for _ in range(n + 1)] d[1][0] = a[1] d[1][1] = b[1] for i in range(2, n + 1): d[i][0] = max( max(d[i - 2][0], d[i - 2][1]) + a[i], d[i - 1][1] + a[i], ) d[i][1] =..

문제 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 """ 계단 수: 인접한 모든 자리의 차이가 1이다. 2자리 이상인 경우 마지막으로 끝나는 수: 0, 9 => 1개씩만 존재 나머지는 2개씩 존재 """ n = int(input()) MOD = 1000000000 def solution(n): d = [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0] for _ in range(n + 1)] d[1] = [0, 1, 1, 1, 1, 1, 1, 1, 1, 1] for i in range(2, n + 1): for j in range(10): if j == 0: d[i][j] = d[i - 1][1] % MOD c..

문제 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 풀이 """ RGB 거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다. 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 모든 집을 칠하는 비용의 최솟값은? 1. 1번 집의 색은 2번 집의 색과 같지 않아야 한다. 2. N번 집의 색은 N-1번 집의 색과 같지 않아야한다. 3. i번째 집의 색은 i-1번 / i+1번 집의 색과 같지 않아야 한다. """ import sys n = int..

문제 18353번: 병사 배치하기 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 2,000) 둘째 줄에 각 병사의 전투력이 공백을 기준으로 구분되어 차례대로 주어진다. 각 병사의 전투력은 10,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 import sys n = int(sys.stdin.readline().rstrip()) numbers = [0] + list(map(int, sys.stdin.readline().rstrip().split())) def soluion(a): d = [1] * len(a) for i in range(1, len(a)): for j in range(1, i): if a[i] < a[j] and d[i] < d[j] + 1: d[i] = d[j]..

문제 11060번: 점프 점프 재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로 www.acmicpc.net 풀이 """ Ai 이하만큼 오른쪽으로 떨어진 칸으로 한 번에 점프할 수 있다. 미로의 가장 왼쪽 끝에 있고, 가장 오른쪽 끝으로 가려고 한다. 최소 몇 번 점프를 해야 갈 수 있는지 구하시오. 가장 오른쪽 끝으로 갈 수 없는 경우에는 -1을 출력 d[n]: n칸에 도달했을 때, 최소 점프 횟수. 10 1 2 0 1 3 2 1 5 4 2 10 1 0 0 0 0 0 0 0 1 0 """ import sys n = int(sys.stdin.readlin..

문제 15990번: 1, 2, 3 더하기 5 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 """ 1 = 1 2 = 2 3 = 1 + 2 2 + 1 3 4 = 1 + 2 + 1 (3을 만들 수 있는 경우 중 2개) 1 + 3 3 + 1 (1을 만들 수 있는 경우 중 1개) 5 = 1 + 3 + 1 2 + 1 + 2 3 + 2 2 + 3 6 = 2 + 1 + 2 + 1 2 + 3 + 1 3 + 2 + 1 1 + 2 + 1 + 2 1 + 3 + 2 3 + 1 + 2 1 + 2 + 3 2 + 1 + 3 """ import sys MOD = 1000000009 t = int(sys.stdin.read..