Programming
-
[백준] 2887번 행성 터널 (by Python)Programming/Algorithm 2021. 3. 13. 23:36
문제 https://www.acmicpc.net/problem/2887 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net 풀이 문제를 보고 사이클을 생성하지 않는 범위 내에서 비용이 적은 순으로 edge를 (v - 1)개까지 선택하는 크루스칼 알고리즘이라는 걸 알 수 있다. 나는 처음에 min(|xA-xB|, |yA-yB|, |zA-zB|) 라고 제시된 각 edge의 비용을 모든 A와 B에 대해 계산하여 시간 초과를 마주하게 되었다. 그리고 좀 더 고민해본 결과 모든 좌표들의 x..
-
[백준] 6064번 카잉 달력 (by Python)Programming/Algorithm 2021. 3. 7. 20:33
문제 https://www.acmicpc.net/problem/6064 6064번: 카잉 달력 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터는 한 줄로 구성된다. www.acmicpc.net 풀이 from math import gcd import sys input = sys.stdin.readline t = int(input()) for _ in range(t): m, n, x, y = map(int, input().split()) if n > m: m, n = n, m x, y = y, x k = x y = 0 if n == y else y end = (m * n) // gcd(m..
-
[백준] 1248번 맞춰봐 (by Python)Programming/Algorithm 2021. 3. 7. 20:24
문제 https://www.acmicpc.net/problem/1248 1248번: 맞춰봐 첫째 줄에 수열의 크기 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 둘째 줄에는 N(N+1)/2 길이의 문자열이 주어진다. 처음 N개의 문자는 부호 배열의 첫 번째 줄에 해당하고, 다음 N-1개의 문 www.acmicpc.net 풀이 def backtrack(k, stack): temp = k candidates = range(-10, 11) for i in range(k + 1): now = a[temp] if now == '+': candidates = [c for c in candidates if (sum(stack[i:k]) + c) > 0] elif now == '-': candidates = ..
-
[백준] 1525번 퍼즐 (by Python)Programming/Algorithm 2021. 3. 5. 17:52
문제 https://www.acmicpc.net/problem/1525 1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmicpc.net 풀이 from collections import deque s = '' goal = '123456780' for _ in range(3): s += ''.join(input().split()) visited = {s: True} adj = [[1, 3], [0, 2, 4], [1, 5], [0, 4, 6], [1, 3, 5, 7], [2, 4, 8], [3, 7], [4, 6, 8], [5, 7]] ans = -1 time = 0 q = deque() q.append(..
-
[백준] 14889번 스타트와 링크 (by Python)Programming/Algorithm 2021. 3. 2. 17:42
문제 https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 첫 번째 풀이 처음 생각하게 된 풀이는 브루트 포스 방식입니다. itertools의 combination을 이용해 가능한 조합들을 모두 구하고 그에 따른 각 팀의 능력차를 구하는 방법인데, 여기서 (1, 2, 3, 4) / (5, 6, 7, 8)로 팀이 나뉘었을 때와 (5, 6, 7, 8) / (1, 2, 3, 4)로 팀이 나뉘었을 때를 별도의 경우로 보면 시간복잡도가 더 커지므로 이를 해소하기 위해 우리 팀에는..
-
[백준] 1107번 리모컨 (by Python)Programming/Algorithm 2021. 2. 28. 19:51
문제 https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 풀이 nums = set(['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']) n = int(input()) m = int(input()) if m: broken = set(input().split()) nums -= broken ans = abs(n - 100) if nums: i = 0 while True: left = 0 if n ..
-
[백준] 9663번 N-Queen (by Python)Programming/Algorithm 2021. 2. 28. 17:54
문제 https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 def n_queens(col, i): if (promising(col, i)): if i == n: global ans ans += 1 else: for j in range(1, n + 1): col[i + 1] = j n_queens(col, i + 1) def promising(col, i): k = 1 flag = True while k < i and flag: if col[i] == col[k..
-
[백준] 2225번 합분해 (by Python)Programming/Algorithm 2021. 2. 28. 17:34
문제 0 이상 N 이하의 정수 K개를 더해 N을 만든다고 할 때, K가 1이면 N이 어떤 수든 방법은 1가지이다. 이러한 리스트를 dp_k로 나타낸다고 하면 dp_1은 길이가 n인 [1, 1, 1, 1 ...] 의 모습을 하고 있을 것이다. 그리고 2 이상의 k에 대해서는 dp_k[i] = sum(dp[:i + 1])이다. 풀이 n, k = map(int, input().split()) dp = [1] * (n + 1) k -= 1 while k: next_dp = [1] * (n + 1) for i in range(1, n + 1): next_dp[i] = sum(dp[:i + 1]) dp = next_dp[:] k -= 1 print(dp[-1] % 1000000000)