백준 9658 돌게임4 Silver I 문제링크 9658번: 돌 게임 4 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. www.acmicpc.net 나의 접근 N이 1, 2, 3, 4인 경우를 살펴보았을 때 아래와 같은 패턴이 나타난다: 돌 1개: 상근, 창영 -> 상근 승 돌 2개: 상근, 창영, 상근 -> 창영 승 돌 3개: 상근, 창영, 상근, 창영 -> 상근 승 돌 4개: 상근, 창영, 상근, 창영, 상근 -> 창영 승 N이 5개인 경우부터는 상근이는 돌 1개, 3개, 4개를 고를 수 있다. 위의 패턴을 토대로 각각의 경우에 대한 승패를 살펴보자면: 돌 1개 (남은 돌 네개) -> 창영 승 돌 3개 (남은 돌 2개) -> 창영 승 돌 4개 (남은 돌 1개) -> 상근 승..
백준 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..
