로그 남기기

1463 - 1로 만들기 문제 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 코드 N = int(input()) dp = [0] * (N+1) for i in range(2, N+1): dp[i] = dp[i-1] + 1 if i % 3 == 0: dp[i] = min(dp[i], dp[i//3] + 1) if i % 2 == 0: dp[i] = min(dp[i], dp[i//2] + 1) print(dp[N]) 한마디 memoization 방식을 이용해 d..

11726 - 2 X n 타일링 문제 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 코드 N = int(input()) dp = [0] * (N+1) if N == 1: print(1) elif N == 2: print(2) else: dp[1], dp[2] = 1, 2 for i in range(3, N+1): dp[i] = dp[i-1] + dp[i-2] print(dp[N] % 10007) 한마디 손으로 조금만 그려보면 점화식을 쉽게 찾을 수 있다. 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www..

1316 - 그룹 단어 체커 문제 그룹 단어란 단어에 존재하는 모든 문자에 대해서, 각 문자가 연속해서 나타나는 경우만을 말한다. 예를 들면, ccazzzzbb는 c, a, z, b가 모두 연속해서 나타나고, kin도 k, i, n이 연속해서 나타나기 때문에 그룹 단어이지만, aabbbccb는 b가 떨어져서 나타나기 때문에 그룹 단어가 아니다. 단어 N개를 입력으로 받아 그룹 단어의 개수를 출력하는 프로그램을 작성하시오. 코드 N = int(input()) result = 0 words = [list(input()) for _ in range(N)] for word in words: dic = dict() flag = True for i in range(len(word)): if word[i] not i..

1707 - 이분 그래프 문제 그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다. 그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오. 코드 from collections import deque def bfs(n, visited, check): q = deque() q.append(n) visited[n] = True check[n] = 1 while q: x = q.popleft() for nx in graph[x]: if not visited[nx]: q.append(nx) check[nx] = check[x] * -1..

7453 - 합이 0인 네 정수 문제 정수로 이루어진 크기가 같은 배열 A, B, C, D가 있다. A[a], B[b], C[c], D[d]의 합이 0인 (a, b, c, d) 쌍의 개수를 구하는 프로그램을 작성하시오. 코드 from collections import defaultdict import sys input = sys.stdin.readline N = int(input()) A, B, C, D = [], [], [], [] for _ in range(N): a, b, c, d = map(int, input().split()) A.append(a) B.append(b) C.append(c) D.append(d) AB = defaultdict(int) for i in range(N): for j ..

3079 - 입국심사 문제 상근이와 친구들은 오스트레일리아로 여행을 떠났다. 상근이와 친구들은 총 M명이고, 지금 공항에서 한 줄로 서서 입국심사를 기다리고 있다. 입국심사대는 총 N개가 있다. 각 입국심사관이 심사를 하는데 걸리는 시간은 사람마다 모두 다르다. k번 심사대에 앉아있는 심사관이 한 명을 심사를 하는데 드는 시간은 Tk이다. 가장 처음에 모든 심사대는 비어있고, 심사를 할 준비를 모두 끝냈다. 상근이와 친구들은 비행기 하나를 전세내고 놀러갔기 때문에, 지금 심사를 기다리고 있는 사람은 모두 상근이와 친구들이다. 한 심사대에서는 한 번에 한 사람만 심사를 할 수 있다. 가장 앞에 서 있는 사람은 비어있는 심사대가 보이면 거기로 가서 심사를 받을 수 있다. 하지만 항상 이동을 해야 하는 것은 ..