bfs로 풀어주었다. from collections import deque import sys input = sys.stdin.readline N = int(input()) G = [[] for i in range(N+1)] for _ in range(N-1): a, b = map(int, input().split()) G[a].append(b) G[b].append(a) q=deque() q.append(1) ancestor = {} checked = [0] * (N+1) while q: parent = q.popleft() for i in G[parent]: if not checked[i]: ancestor[i] = parent q.append(i) checked[i] = 1 for i in rang..

from collections import deque import sys input = sys.stdin.readline N, M = map(int,input().split()) G = [[] for _ in range(N+1)] visited = [0] * (N+1) for _ in range(M): u, v = map(int, input().split()) G[u].append(v) G[v].append(u) q = deque() connect = 0 for i in range(1,N+1): #만약 방문하지 않았으면 if visited[i] == 0: #방문 처리 해주고 visited[i] = 1 #큐에 추가 q.append(i) #연결되는 갯수 늘어났으므로 하나 추가 connect += 1 #큐가 ..

다리를 그림으로 그리고 규칙성을 파악하면 쉽게 풀 수 있는 문제이다. 첫번째 n의 다리와 첫번째 m의 다리를 이어놓고 그 아래의 다리를 보면, 이전에 적용된 다리의 경우의 수가 계속 적용되어 나옴을 확인할 수 있다. n이 1일 경우 m과 같아서 for문 이용해서 미리 만들어주고 그 아래에 위의 공통된 로직을 짜면 된다. 전형적인 dp문제이지만 다른 사람들 풀이를 보니 조합을 이용해서도 많이 푼 것 같다. # https://www.acmicpc.net/problem/1010 array = [[0] * 30 for _ in range(30)] for i in range(1, 30): array[1][i] = i for i in range(2, 30): for j in range(i, 30): for k in..

# https://www.acmicpc.net/problem/13301 # 표로 정리하면 금방 규칙성을 파악할 수 있다. # 타일 개수 1 2 3 4 5 6 7 # 둘레 4 6 10 16 26 42 68 # f(n) = f(n-1) + f(n-2) 의 규칙으로 증가함을 알 수 있다. n = int(input()) answer = [0, 4, 6] def get_circumference(n): if n == 1: return 4 if n == 2: return 6 else: for i in range(3, 81): answer.append(answer[i-1] + answer[i-2]) return answer[n] print(get_circumference(n)) 13301번: 타일 장식물 대구 달성공원..

전형적인 dp문제 버튼을 누르는 횟수 별 a와 b횟수를 표로 정리하면 금방 해결방법을 찾을 수 있다. /누르는 횟수 0 1 2 3 결과 A B BA BAB A개수 1 0 1 1 B개수 0 1 1 2 각각의 a,b 개수 별로 현재 인덱스의 개수 = 전 인덱스 개수 + 전전 인덱스 개수 의 규칙임을 한 눈에 알 수 있다. # https://www.acmicpc.net/problem/9625 # 전형적인 f(n) = f(n-1) + f(n-2) 구조임 # 입력 : 버튼 눌리는 횟수: k # 출력 : 사용자가 k번 눌렀을때 결과창에 뜬 a 개수와 b의 개수 k = int(input()) #버튼을 누른 횟수 만큼 a횟수와 b횟수를 각각 나누어 배열로 정리해 보자면 다음과 같다. #클릭:0 1 a = [1, 0] ..