목록Computer Science (228)
DHistory
문제 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 풀이 BFS나 DFS를 이용하여 모든 도시로 갈 수 있는 최단의 거리를 구한다. 이 후 최단 거리에 도달한 도시만 출력한다. import sys from collections import deque INF = 1e9 n, m, k, x = map(int, sys.stdin.readline().rstrip().split()) distance = [INF] * (n + 1) graph = ..
문제 1495번: 기타리스트 첫째 줄에 N, S, M이 주어진다. (1 ≤ N ≤ 50, 1 ≤ M ≤ 1,000, 0 ≤ S ≤ M) 둘째 줄에는 각 곡이 시작하기 전에 줄 수 있는 볼륨의 차이가 주어진다. 이 값은 1보다 크거나 같고, M보다 작거나 같다. www.acmicpc.net 풀이 현재 볼륨 = 직전 볼륨 ± 현재 조절할 수 있는 볼륨의 크기이다. 해당 문제는 2개의 변수가 있다. 1. index(마지막까지 연주) 2. 볼륨의 크기 이를 만족하기 위해 2중 배열을 생성해야한다. index와 0부터 최대 볼륨의 크기까지 값을 할당한다. 처음 볼륨 크기를 기준으로 현재 볼륨의 크기를 더하거나 빼서 가능한지 확인한다. 이 후, 마지막 배열(마지막 곡 연주)에서 가능한 볼륨의 크기 중 가장 큰 값을..
문제 10164번: 격자상의 경로 입력의 첫째 줄에는 격자의 행의 수와 열의 수를 나타내는 두 정수 N과 M(1 ≤ N, M ≤ 15), 그리고 ○로 표시된 칸의 번호를 나타내는 정수 K(K=0 또는 1 < K < N×M)가 차례로 주어지며, 각 값은 공백으 www.acmicpc.net 풀이 경우의 수 = 현재 좌표 기준으로 왼쪽에서 들어오는 경우와 위쪽에서 들어오는 경우를 더하면 된다. 1. k가 없는 경우는 전체 경우의 수를 구하면 된다. 2. k가 있는 경우 k를 기준으로 1, 3 사분면(X 표시)에는 도달할 수 없으므로 경우의 수를 계산하지 않는다. n, m, k = map(int, input().split()) d = [[0] * (m + 1) for _ in range(n + 1)] index..
문제 2302번: 극장 좌석 주어진 조건을 만족하면서 사람들이 좌석에 앉을 수 있는 방법의 가짓수를 출력한다. 방법의 가짓수는 2,000,000,000을 넘지 않는다. (2,000,000,000 < 231-1) www.acmicpc.net 풀이 1. 극장 좌석은 최대 40개의 의자를 놓을 수 있으므로 40개가 들어갈 수 있는 배열을 초기화한다. 2. d[n]은 극장 좌석이 n개일 때, 자리에 앉을 수 있는 경우의 수다. 2-1. n자리가 될 때, 자리를 바꾸지 않는 경우 (맨 오른쪽에 앉게 됨) 2-2. n자리가 될 때, 자리를 바꿔 않는 경우 (맨 오른쪽에서 두번째에 앉게 됨) 2-3. 즉, d[n] = d[n - 1] + d[n - 2]가 극장 좌석이 n자리 일 때, 자리에 앉을 수 있는 경우의 수가..
문제 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..