백준 1793 타일링 Silver I 문제링크 1793번: 타일링 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 숫자 0 ≤ n ≤ 250이 주어진다. www.acmicpc.net 나의 접근 DP로 타일링에 대한 규칙을 찾고 그에 대한 점화식을 찾아내는 문제다. 한 칸을 채우는 방법은 세로로 타일을 배치하는 방법 하나, 두 칸을 채우는 방법은 가로로 타일을 2개 배치하는 방법과 2x2 타일을 배치하는 방법 2개이기 때문에 arr[i] = arr[i - 1] + 2 * arr[i - 2] 과 같은 점화식이 나온다. N = 0 인 경우에도 답은 1이고 (아무것도 안하는 방법도 하나의 방법이기 때문), 명시되지 않는 M개의 테스트케이스를 한 번에 인풋으로 받아..
백준 2407 조합 Silver II 문제링크 2407번: 조합 n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n) www.acmicpc.net 나의 접근 nCr을 구하는 문제로, 동적계획법으로 n! / r!(n - r)! 를 계산하면 된다. 팩토리얼을 어떻게 구현하는 것이 관건이다. N번째에 해당하는 factorial을 재귀적으로 계산해나가며 딕셔너리에 key, value로 저장한다. import sys N, R = map(int, sys.stdin.readline().split()) def dp(num): arr = {} if num in arr: return arr[num] elif num == 0 or num == 1: arr[num] = 1 return 1 else..
백준 3055 탈출 Gold V 문제링크 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 나의 접근 너비 우선 탐색으로 한시간이 지날때마다 물에 대한 경로탐색 및 이동 후, 고슴도치에 대한 경로 탐색 및 이동을 진행해야한다. 처음에는 단순 BFS로 구현했다가 당연히 시간초과가 떴다. Deque을 사용하고, 미리 선언해놓은 N 길이의 배열에 거리를 저장해준다. from collections import deque def bfs(x, y): q.append([x, y]) mapp[x][y] = 1 dx = [1, -1, 0,..
