백준 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,..
백준 1806 부분합 Gold IV 문제링크 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 나의 코드 N, S = map(int, input().split()) A = list(map(int, input().split())) sum_A = [0] * (N + 1) for i in range(1, N + 1): sum_A[i] = sum_A[i-1] + A[i-1] answer = 1000001 start = 0 end = 1 while start != N: if sum_A[end] - sum_..
