2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net import sys sys.setrecursionlimit(10**6) input=sys.stdin.readline # 네 방향 탐색을 위한 상수 → ↓ ← ↑ dr=[0,1,0,-1] dc=[1,0,-1,0] n=int(input()) graph=[list(map(int, input().split())) for _ in range(n)] # print(graph) def DFS(i,j,h): visited[i][j]=True for d in range(4): next..

2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 6 8 2 6 2 3 2 3 4 6 6 7 3 3 2 7 2 5 3 6 8 9 5 2 7 """ 어떤 지역의 높이 정보를 파악, 많은 비가 내렸을 때 물에 잠기지 않는 안전한 영역 최대 몇 개인지 조사 비의 양에 따라 일정한 높이 이하의 모든 지점은 물에 잠김 안전영역 : 물에 잠기지 않는 지점들이 위, 아래, 오른쪽 혹은 왼쪽으로 인접해 있으며 그 크기가 최대인 영역 높이가 4 이하인 모든 지점이 물에 잠김 내리는 비의 양에 따른 모든 경우를 다 조사해 보면 물에 잠..

2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 분석 [17472] 다리 만들기2 (BFS, MST) 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바 karla.tistory.com 풀이 """ 1은 집이 있는 곳을, 0은 집이 없는 곳 연결된 집들의 모임인 단지를 정의하고, 단지에 번호 붙이려한다 단지수를 출력, 각 단지 에 속하는 집의 수를 오름..

2011번: 암호코드 나올 수 있는 해석의 가짓수를 구하시오. 정답이 매우 클 수 있으므로, 1000000으로 나눈 나머지를 출력한다. 암호가 잘못되어 암호를 해석할 수 없는 경우에는 0을 출력한다. www.acmicpc.net 분석 10 ≤ 현재 숫자와 바로 그 앞자리 숫자 ≤ 26일 때, 두자리가 가능한 숫자 dp[i] += dp[i-2] : 앞자리 숫자 앞의 DP[현재숫자인덱스-2]에 저장되어있는 값을 DP[현재숫자]에 넣어줌 1 ≤ 현재 숫자 ≤ 9 dp[i] += dp[i-1] : 앞자리 숫자의 DP[앞자리숫자] 또한 DP[현재숫자]에 넣어줌 풀이 code = list(map(int, input())) n = len(code) dp=[0]*(n+1) dp[0]=1 dp[1]=1 if code[0..

2624번: 동전 바꿔주기 명보네 동네 가게의 현금 출납기에는 k 가지 동전이 각각 n1, n2, … , nk개 씩 들어있다. 가게 주인은 명보에게 T원의 지폐를 동전으로 바꿔 주려고 한다. 이때, 동전 교환 방법은 여러 가지가 있을 www.acmicpc.net 분석 dp[i][j] : i번째 동전까지 사용해서 j원을 만들 수 있는 경우의 수 dp[money] += dp[money - coin * cnt] (money는 구하기 위한 금액, coin은 현재 사용하는 동전의 금액, cnt는 사용하는 동전의 개수) 풀이 """ 입력으로 지폐의 금액 T 동전의 가지 수 k 각 동전 하나의 금액 pi와 개수 ni가 주어질 때 (i=1, 2,…, k) 지폐를 동전으로 교환하는 방법의 가지 수 """ t=int(i..

17610번: 양팔저울 무게가 서로 다른 k개의 추와 빈 그릇이 있다. 모든 추의 무게는 정수이고, 그릇의 무게는 0으로 간주한다. 양팔저울을 한 번만 이용하여 원하는 무게의 물을 그릇에 담고자 한다. 주어진 모든 추 www.acmicpc.net 분석 풀이 """ 무게가 서로 다른 K개의 추, 모든 추 무게의 합 S {1, 5, 7}이면 S=13이고, 그릇에 담을 수 있는 물의 무게는 {1, 2, 3, 4, 5, 6, 7, 8, 11, 12, 13}이고, 1부터 S사이에서 무게에서 9와 10에 대응하는 무게의 물을 담을 수 없다. K(3