개발 일지

문제 1463번: 1로 만들기 (acmicpc.net) 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 풀이 예를 들어 X가 6인 경우, dp[6] = min(dp[5],dp[3],dp[2]) + 1이 될 것이다. 즉 X가 2로 나눠지는 경우와 3으로 나눠지는 경우에 대해서 점화식을 세우면 된다. N = int(input()) dp = [0]*(10**6+1) dp[1],dp[2],dp[3] = 0,1,1 for i in range(4,N+1): dp[i] = dp[i-1] + 1 if i%2 == 0: dp[i] = min(dp[i], dp[i//2]+1) if i%3 == 0: dp[i] = min(dp[i], dp[i..

문제 2579번: 계단 오르기 (acmicpc.net) 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 풀이 N 번째 계단을 반드시 밟으면서 계단 값들의 합이 최대가 되는 경우는, N-3번째 계단과 N-1번째 계단을 밟는 경우가 있고 N-2번째 계단만 밟는 경우가 있다. 조건에 의해 3번 연속 계단을 밟을 수 없기 때문이다. N = int(input()) stairs = [0]*10001 for i in range(1,N+1): stairs[i] = int(input()) dp = [0]*10001 dp[1] = stai..

문제 1149번: RGB거리 (acmicpc.net) 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 풀이 어떤 시점 i에서 고를 수 있는 색은 총 세가지가 있으므로, 세 가지 색에 대해서 비용이 최소가 되게끔 dp를 작성하면 된다. N = int(input()) rgb = [[]] for _ in range(N): rgb.append(list(map(int,input().split()))) dp = [[0]*3 for _ in range(N+1)] for i in range(1,N+1)..

문제 1912번: 연속합 (acmicpc.net) 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 풀이 적분으로 생각하면 좀 더 쉽게 접근 가능하다. 회색이 입력으로 주어지는 값들의 그래프, 노란색이 적분 그래프, 주황색이 dp 그래프이다. 구간합은 적분그래프에서 F(x) - F(x-1) 와 같기 때문에 F(x)가 0 이하인 시점부터는 구간합을 적분값이 아닌 원래 그래프 값 f(x)로 정해주면 된다. 그림이 살짝 잘못됐는데, F(x) = 0 이 되는 시점부터 주황색선은 y(x)를 따라가다가 y(x)가 0 이상이 되는 시..

문제 17822번: 원판 돌리기 (acmicpc.net) 17822번: 원판 돌리기 반지름이 1, 2, ..., N인 원판이 크기가 작아지는 순으로 바닥에 놓여있고, 원판의 중심은 모두 같다. 원판의 반지름이 i이면, 그 원판을 i번째 원판이라고 한다. 각각의 원판에는 M개의 정수가 적혀 www.acmicpc.net 풀이 간단한 구현 문제지만, 각 행이 큐로 되어있어 인접 노드를 탐색할 때 주의해야한다. 어이없게도 "배수"를 반복문을 통해 2배씩 곱해주는 것으로 계산해서 많은 시간을 날렸다. 또한 평균을 구할 때 cnt 가 0이 되는 때도 있음을 주의해야한다. from collections import deque N,M,T = map(int,input().split()) # 0:W 1:R 2:B circ..

문제 15686번: 치킨 배달 (acmicpc.net) 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 풀이 사다리 조작 문제와 동일한 조합 문제이다. 치킨집을 최대 M개 까지 남길 수 있고, M개 이하의 가능한 조합을 짜보면서 최소가 되는 도시 치킨 거리를 갱신한다. 치킨집은 최대 13개, 가정집은 최대 2N개 까지만 존재할 수 있으므로 따로 좌표를 리스트에 넣어놓고 1차원 리스트에 대해 조합을 짜도 된다. N,M = map(int,input().split()) board = [[0]*(..

문제 23291번: 어항 정리 (acmicpc.net) 23291번: 어항 정리 마법사 상어는 그동안 배운 마법을 이용해 어항을 정리하려고 한다. 어항은 정육면체 모양이고, 한 변의 길이는 모두 1이다. 상어가 가지고 있는 어항은 N개이고, 가장 처음에 어항은 일렬로 바 www.acmicpc.net 풀이 요구사항이 꽤 많은데, 차근차근 정리하며 구현하는것이 중요하다. 어항에 물고기 넣기 가장 물고기 숫자가 적은 어항에 물고기를 한마리 씩 넣어야 하므로, 어항 일차원 리스트를 정렬한 뒤 upper bound로 물고기를 넣어줘야하는 어항 인덱스를 찾았다. 공중부양 쌓기 1 맨 왼쪽 어항을 그 옆에있는 어항위에 쌓은 뒤, 조건에 따라 어항을 쌓아간다. 왼쪽에 몰려있는 두개 이상 쌓여있는 어항들을 빼서 90도 ..

문제 23290번: 마법사 상어와 복제 (acmicpc.net) 23290번: 마법사 상어와 복제 첫째 줄에 물고기의 수 M, 상어가 마법을 연습한 횟수 S가 주어진다. 둘째 줄부터 M개의 줄에는 물고기의 정보 fx, fy, d가 주어진다. (fx, fy)는 물고기의 위치를 의미하고, d는 방향을 의미한다. 방향 www.acmicpc.net 풀이 물고기의 이동 제한 조건은 상어의 존재, 보드 경계 그리고 냄새이다. 냄새는 생성되는 턴에 한번, 그리고 그로부터 두턴 더 남아있기 때문에 총 세번의 반복문을 돌고나면 0이된다는 점에 주의하자. 상어는 최적의 이동경로를 먼저 탐색한 뒤 그 경로를 따라 이동한다. 경로 탐색은 이동경로에 있는 물고기 숫자의 합과 이동경로 자체에 의해 결정되는데, 이는 heapq를 ..

문제 21611번: 마법사 상어와 블리자드 (acmicpc.net) 21611번: 마법사 상어와 블리자드 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그, 비바라기 마법을 할 수 있다. 오늘 새로 배운 마법은 블리자드이고, 크기가 N×N인 격자에서 연습하려고 한다. N은 항상 홀수이고, ( www.acmicpc.net 풀이 풀이에 상당한 시간이 소요된 문제이다. 본 문제에서의 핵심은, 블리자드 마법을 시전할 때외에는 전부 블리자드의 진행방향으로만 보드를 탐색한다는 것이다. 즉 마법 시전 이후엔 매번 보드를 블리자드 진행방향으로 탐색하기 보다는 일차원 리스트로 해석해서 구현하는것이 훨씬 편하다는 점을 눈치채야한다. 블리자드 진행방향에 있는 요소들을 일차원 리스트에 담을때는, 이전 문제들과 마찬가..

문제 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그 마법을 할 수 있다. 오늘 새로 배운 마법은 비바라기이다. 비바라기를 시전하면 하늘에 비구름을 만들 수 있다. 오늘은 비바라기를 크기가 N×N인 격자에서 연습하려고 한다. 격자의 각 칸에는 바구니가 하나 있고, 바구니는 칸 전체를 차지한다. 바구니에 저장할 수 있는 물의 양에는 제한이 없다. (r, c)는 격자의 r행 c열에 있는 바구니를 의미하고, A[r][c]는 (r, c)에 있는 바구니에 저장되어 있는 물의 양을 의미한다. 격자의 가장 왼쪽 윗 칸은 (1, 1)이고, 가장 오른쪽 아랫 칸은 (N, N)이다. 마법사 상어는 연습을 위해 1번 행과 N번 행을 연결했고, 1번 열과 N번 열도 연결했다. 즉, N번 행의 아래에는 1번 행이, ..