문제 www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 풀이 DFS나 BFS를 이용해서 풀 수 있는 기본적인 그래프 탐색 문제다. 코드 BFS import sys, collections while True: w, h = map(int, sys.stdin.readline().split()) if w == 0 and h == 0: break g, lands, visited = [], [], [[0 for _ in range(w)] for _ in range(..
문제 www.acmicpc.net/problem/6603 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net 풀이 간단한 문제다. DFS 탐색이나 조합을 이용해서 풀 수 있다. 코드 from itertools import combinations import sys while True: input = [int(x) for x in sys.stdin.readline().split()] k = input[0] if k == 0: break input = input[1:] combis = list(combin..
문제 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..
