Problem Solving
-
[백준] 1904번 문제 (01타일) 파이썬(Python) 풀이Problem Solving/Baekjoon 2021. 9. 14. 15:07
https://www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net n = int(input()) dp = [0] * 1000001 dp[1], dp[2] = 1, 2 for i in range(3, n + 1): dp[i] = (dp[i - 1] + dp[i - 2]) % 15746 print(dp[n]) 경우의 수를 차근 차근 구해보니 규칙을 발견할 수 있었다. 입력받은 숫자 n에 대하여 규칙은 아래와 같다. n 2진 수열의 개수 1 1 2 2 3 3 4 5 5 8..
-
[백준] 11279번 문제 (최대 힙) 파이썬(Python) 풀이Problem Solving/Baekjoon 2021. 9. 14. 15:00
https://www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 www.acmicpc.net import heapq import sys input = sys.stdin.readline t = int(input()) heap = [] for _ in range(t): cmd = int(input()) if cmd == 0: try: print(heapq.heappop(heap)[1]) except: print(0) else: heapq.heappush(heap, (-cm..
-
[백준] 1927번 문제 (최소 힙) 파이썬(Python) 풀이Problem Solving/Baekjoon 2021. 9. 14. 14:55
https://www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net import heapq import sys input = sys.stdin.readline t = int(input()) heap = [] for _ in range(t): cmd = int(input()) if cmd == 0: try: print(heapq.heappop(heap)) except: print(0) else: heapq.heappush(heap, cmd) 최소..
-
[백준] 7569번 문제 (토마토) 파이썬(Python) 풀이Problem Solving/Baekjoon 2021. 9. 10. 10:15
https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net import sys from collections import deque input = sys.stdin.readline q = deque() def bfs(): global result while q: qh, qn, qm = q.popleft() for d in range(6): nh = qh + dh[d] nn = qn + dn[d] nm = qm + dm[d] if 0
-
[백준] 12852번 문제 (1로 만들기 2) 파이썬(Python) 풀이Problem Solving/Baekjoon 2021. 9. 9. 17:21
https://www.acmicpc.net/problem/12852 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net n = int(input()) dp = [i for i in range(n + 1)] dp[1] = 0 history = [i for i in range(n + 1)] history[1] = 0 for i in range(2, n + 1): dp[i] = dp[i - 1] + 1 history[i] = i - 1 if i % 3 == 0 and dp[i] > dp[i // 3] + 1: dp[i] = dp[i // 3] + 1 history[i] = i // 3 if i % 2 == 0 and dp[i..
-
[백준] 1021번 문제 (회전하는 큐) 파이썬(Python) 풀이Problem Solving/Baekjoon 2021. 9. 9. 09:34
https://www.acmicpc.net/problem/1021 1021번: 회전하는 큐 첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 www.acmicpc.net from collections import deque from sys import stdin input = stdin.readline n, m = map(int, input().split()) target_nums = deque(list(map(int, input().split()))) q = deque([i for i in range(1, n + 1)]) count = 0 while len(..
-
[백준] 16948번 문제 (데스나이트) 파이썬(Python) 풀이Problem Solving/Baekjoon 2021. 9. 7. 15:55
https://www.acmicpc.net/problem/16948 16948번: 데스 나이트 게임을 좋아하는 큐브러버는 체스에서 사용할 새로운 말 "데스 나이트"를 만들었다. 데스 나이트가 있는 곳이 (r, c)라면, (r-2, c-1), (r-2, c+1), (r, c-2), (r, c+2), (r+2, c-1), (r+2, c+1)로 이동할 수 있다. 크 www.acmicpc.net from collections import deque def bfs(y, x): q = deque() q.append((y, x)) graph[y][x] = 0 while q: y, x = q.popleft() for dy, dx in d: ny, nx = y+dy, x+dx if 0
-
[백준] 1010번 문제 (다리 놓기) 파이썬(Python) 풀이Problem Solving/Baekjoon 2021. 9. 7. 13:20
https://www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net dp = [[1] * 31 for _ in range(31)] for i in range(31): dp[1][i] = i for i in range(2, 31): for j in range(i + 1, 31): dp[i][j] = dp[i][j - 1] + dp[i - 1][j - 1] t = int(input()) for _ in range(t): n, m = map(int, input().sp..
-
[백준] 5567번 문제 (결혼식) 파이썬(Python) 풀이Problem Solving/Baekjoon 2021. 9. 7. 10:53
https://www.acmicpc.net/problem/5567 5567번: 결혼식 예제 1의 경우 2와 3은 상근이의 친구이다. 또, 3과 4는 친구이기 때문에, 4는 상근이의 친구의 친구이다. 5와 6은 친구도 아니고, 친구의 친구도 아니다. 따라서 2, 3, 4 3명의 친구를 결혼식에 초대 www.acmicpc.net import sys import collections input = sys.stdin.readline n = int(input()) m = int(input()) graph = collections.defaultdict(list) friends = set() for i in range(m): a, b = map(int, input().split()) graph[a].append(b)..