흙금이네 블로그

아이디어 동적 계획법으로 서로 인접하지 않은 색을 고를 수 있는 경우의 수를 구한다. 풀이 def solution(): N = int(input()) K = int(input()) p = 1000000003 if K > N//2: print(0) return dp = [[0]*N for _ in range(N//2+1)] dp[1] = [1]*N for i in range(2, N//2+1): for j in range(N-3): dp[i][j+2] = (dp[i][j+1]+dp[i-1][j])%p dp[i][-1] = dp[i][-2] res = 0 for j in range(N): res = (res+dp[K][j])%p print(res) solution()

아이디어 #1 BFS로 세 그룹의 돌이 개수가 같아질 수 있는지 확인한다. 풀이 #1 import sys input = sys.stdin.readline def solution(): A, B, C = map(int, input().split()) if (A+B+C)%3: print(0) else: visited = dict() queue = [tuple(sorted([A, B, C]))] visited[queue[0]] = 1 while queue: a, b, c = queue.pop(0) if a == b == c: print(1) break if a != b: temp = tuple(sorted([a+a, b-a, c])) if visited.get(temp, 0) == 0: visited[temp]..

아이디어 유니온 파인드로 한 개 이상의 변이 만나는 직사각형들의 집합 개수를 구한다. 풀이 (0, 0)을 지나는 직사각형을 고려해 (0, 0)에 크기가 0인 직사각형을 하나 추가하고, 직사각형 집합 개수-1을 출력한다. import sys input = sys.stdin.readline def solution(): def find(n): temp = n while n != group[n]: n = group[n] group[temp] = n return n def union(n1, n2): n1 = find(n1) n2 = find(n2) if n1 > n2: n1, n2 = n2, n1 group[n2] = n1 N = int(input()) group = [i for i in range(N+1)] r..

아이디어 체스판을 갱신하며 9초 이상 캐릭터가 이동할 수 있는지 확인한다. 풀이 delta = [(0, 0), (-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)] def solution(): board = [[*input()] for _ in range(8)] visited = [[0]*8 for _ in range(8)] visited[7][0] = 1 stack = [(7, 0)] t = 1 while stack and t nr >= 0 and 8 > nc ..

아이디어 BFS로 방문하는 칸에 거울을 설치할 수 있는지에 따라 방향을 회전하며 설치해야 할 거울의 최소 개수를 구한다. 풀이 import sys input = sys.stdin.readline delta = [(-1, 0), (0, 1), (1, 0), (0, -1)] def solution(): N = int(input()) board = [[*input().rstrip()] for _ in range(N)] doors = [] for r in range(N): for c in range(N): if board[r][c] == '#': doors.append((r, c)) stack = [] for d in range(4): stack.append((*doors[0], d)) cnt = 1 while..

아이디어 벨만-포드로 1번 도시에서 나머지 도시로 가는 가장 빠른 시간과 음의 사이클 여부를 확인한다. 풀이 두 도시 간 버스 노선이 여러 개일 수 있으므로 두 도시 간 이동 시간이 최소인 노선 정보를 저장한다. import sys input = sys.stdin.readline INF = int(1e11) def solution(): N, M = map(int, input().split()) graph = [dict() for _ in range(N+1)] for _ in range(M): A, B, C = map(int, input().split()) graph[A][B] = min(graph[A].get(B, INF), C) D = [INF]*(N+1) D[1] = 0 for _ in range(N..

아이디어 이분 탐색으로 가능한 최소 차이를 찾아 나가며, 방문할 칸의 값 범위를 제한하여 여러 경로를 방문할 수 있도록 한다. 풀이 import sys input = sys.stdin.readline delta = [(-1, 0), (0, 1), (1, 0), (0, -1)] def solution(): n = int(input()) board = [] numbers = set() for _ in range(n): board.append(tuple(map(int, input().split()))) numbers.update({*board[-1]}) numbers = sorted(numbers) s, e = 0, numbers[-1]-numbers[0] while s = board[0][0] >= i: v..

아이디어 #1 세트를 이용해 연산을 K번 수행했을 때 나올 수 있는 수의 최댓값을 구한다. 풀이 #1 def solution(): N, K = input().split() K = int(K) M = len(N) numbers = [set() for _ in range(K+1)] numbers[0].add(N) for k in range(K): for number in numbers[k]: num = [*number] for i in range(M-1): for j in range(i+1, M): if i == 0 and num[j] == '0': continue num[i], num[j] = num[j], num[i] numbers[k+1].add(''.join(num)) num[i], num[j] = ..

아이디어 BFS로 한 C칸에서 다른 C칸까지의 각 칸에 방문하기 위해 설치해야 할 최소 거울 개수를 구해 나간다. 풀이 import sys input = sys.stdin.readline delta = [(-1, 0), (0, 1), (1, 0), (0, -1)] def solution(): W, H = map(int, input().split()) board = [[*input().rstrip()] for _ in range(H)] visited = [[-1]*W for _ in range(H)] K = max(W, H) points = [] for r in range(H): for c in range(W): if board[r][c] == 'C': points.append((r, c)) stack =..

아이디어 상근이가 있는 감옥 외부와 두 죄수가 있는 칸에서 각각 0-1 BFS로 탐색한다. 모든 칸에 대해 열어야 하는 최소 문 개수들을 구한 후, 세 사람이 만나는 칸의 문 개수 합의 최솟값을 구한다. 풀이 import sys from collections import deque input = sys.stdin.readline delta = [(-1, 0), (0, 1), (1, 0), (0, -1)] def solution(): def bfs(x, y): visited = [[-1]*w for _ in range(h)] visited[x][y] = 0 queue = deque([(x, y, 0)]) while queue: r, c, cnt = queue.popleft() for dr, dc in de..