흙금이네 블로그

아이디어 돌 개수에 따른 결과의 규칙을 찾는다. 풀이 돌 개수가 홀수면 상근이가, 짝수면 창영이가 게임을 이기게 된다. print('SK' if int(input())%2 else 'CY')

아이디어 규칙을 찾고 동적 계획법으로 가짓수를 계산한다. 풀이 고정석으로 구분된 연속된 좌석에 대해 그 가짓수가 좌석 개수에 따라 피보나치 수열을 이루고 있다. 리스트 vip에는 0과 좌석 끝 번호를 추가하여 고정석 번호를 저장하고, 리스트 dp에는 피보나치 수열을 저장한다. 전체 가짓수는 연속된 일반 좌석들의 곱이므로 결과값 res에 일반 좌석 개수에 따른 피보나치 수열의 수를 곱한다. import sys input = sys.stdin.readline def solution(): N = int(input()) M = int(input()) vip = [0]+[int(input()) for _ in range(M)]+[N+1] dp = [1]*(N+1) for i in range(2, N+1): dp[..

아이디어 동적 계획법으로 각 블록을 사용하여 탑을 만드는 경우의 수를 구해 나간다. 풀이 #1 (Python) 2624번 동전 바꿔주기 문제 풀이와 유사하다. 0으로 채워진 H+1 크기의 리스트 dp를 생성하는데, dp[i]에는 높이 i의 탑을 만드는 경우의 수를 저장한다. for문에서 리스트 blocks에 블록들의 높이를 입력 받고, temp에 리스트 dp를 복사하여 저장한다. blocks의 블록 하나로 해당 블록의 높이만큼 탑을 쌓는 경우의 수 dp[b]를 1 증가시키고, 해당 블록을 기존 블록들을 함께 사용해 탑을 쌓아 높이 i의 탑을 경우의 수를 temp[i-b]만큼 증가시킨다. 높이 H의 탑을 쌓는 경우의 수를 10,007로 나눈 나머지를 출력한다. import sys input = sys.st..