문제 www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 풀이 이 문제는 두 가지의 작은 문제로 분할하여 생각해볼 수 있다. 1) 벽을 어떻게 세울 것인가? 2) 어떻게 탐색을 할 것인가? BFS/DFS문제를 어느 정도 접해본 사람이라면 2)는 문제가 되지 않을 것이다. 그러나 문제는 바로 1)이다. 이 문제의 경우엔 n, m의 범위가 작기 때문에 브루트 포스를 이용하면 된다. 재귀를 이용하는 방법도 있지만, 시간을 줄이기 위해 처음 입력을 받을 때부터 빈 칸(0)의 좌표를..
문제 www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 풀이 n개의 카드를 갖기 위해 지불해야 하는 금액 DP[n]은 DP[n-k] + DP[k]으로 표현할 수 있다. 예를 들어 n=5이면 다음과 같다. DP[5] = max(DP[5], DP[4] + DP[1], DP[3] + DP[2]) 즉, 점화식은 그대로 DP[n] = DP[k] + DP[n-k]가 되며 이를 위해 DP[n]엔 모두 P[n]로 초기화했다. 코드 import sys n = int(input()) ..
문제 www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 0을 제외한 모든 숫자는 앞에 올 수 있다. 이때 1~8은 뒤에 올 수 있는 숫자가 총 2종류이다(숫자±1). 하지만 9 뒤엔 오직 숫자 8만이 올 수 있다. 이를 그림으로 표현하면 다음과 같다. dp테이블은 이차원 리스트이며 dp[자리 수][앞에 오는 숫자]=경우의 수이다. 정리하면 다음과 같다. 앞에 오는 숫자 = 0 ) dp[자리 수][0] = dp[자리 수 - 1][1] ※ dp[1][0] = 0이기 때문에 어차피 결과엔 영향을 미치지 않는다. ex) 0, 01, 012 -> 안 셈! 앞에 오는 숫자 = 1..
문제 www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 풀이 이 문제의 핵심은 같은 색으로 연속해서 집을 색칠할 수 없다는 것이다. 다시 말해서 같은 색이 아닌 색으로 다음 집을 칠해야 한다는 것이다. 이것이 점화식을 세우는 핵심이다. 이것을 간단하게 표현하면 다음과 같다. 이전 집의 색깔 현재 집의 색깔 G or B R R or B G R or G B 이를 통해 점화식으로 표현하면 다음과 같다. R, G, B = 0, 1, 2 dp[i]..
문제 www.acmicpc.net/problem/4948 4948번: 베르트랑 공준 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼 www.acmicpc.net 풀이 에라토스테네스의 체를 이용하여 풀었다. 입력의 한계를 고려하여 사용했던 숫자를 기록해둔 후에 중복 계산을 피하는 방식으로 최적화를 했다. 하지만, 먼저 모든 해를 구한 것과 시간 차이는 그리 크지 않았다(30ms). 코드 1번 풀이 N = 123456 max_num = 0 isPrime = [False, False] + [True]*(2*N - 1) def count_num(n): global..
