흙금이네 블로그

아이디어 동적 계획법으로 각 동전을 사용한 교환 방법의 가짓수를 저장해 나간다. 풀이 #1 (Python) 0으로 채워진 T+1 크기의 리스트 dp를 생성하는데, dp[i]에는 i원의 교환 방법 가짓수를 저장한다. for문에서 동전의 금액 p와 동전 개수 n을 입력 받고, temp에 리스트 dp를 복사하여 저장한다. p원 동전으로만 교환하는 방법의 가짓수는 1이므로 n 이하의 자연수 i에 대해 dp[p*i]를 1씩 증가시킨다. p원 동전을 사용하여 교환하는 방법의 수는 그 금액보다 p원만큼 작은 금액을 기존 동전들로 교환하는 방법의 수와 같다. 따라서 기존 동전들과 함께 사용하여 교환하는 방법의 수 dp[j]에 기존 동전들로만 교환하는 방법의 수 dp[j-p*i]를 더한다. 지폐의 금액 T를 넘는 동전의..

아이디어 동적 계획법으로 감소하는 수열 합의 최댓값을 구한다. 풀이 #1 (Python) 리스트 dp에 수열 A와 같은 값들을 저장한다. 이중 for문에서 수열의 두 요소를 비교하여 수가 감소할 때 더 큰 부분 수열의 합으로 갱신해 나간다. max(dp)로 전체 감소 부분 수열의 합 중 가장 큰 값을 찾아 출력한다. def solution(): N = int(input()) A = tuple(map(int, input().split())) dp = list(A) for i in range(N): for j in range(i+1, N): if A[j] dp[j]: dp[j] = dp[i]+A[j] print(max(dp)) solution() 풀이 #2 (Jav..

아이디어 덱을 이용하여 풍선 안 종이에 적힌 수에 따라 풍선을 회전한다. 풀이 덱을 사용하기 위해 collections 모듈의 deque를 불러온다. enumerate 함수를 이용하여 풍선의 번호와 풍선 안 종이에 적힌 수를 튜플 형태로 덱 balloon에 저장한다. for문에서 popleft로 balloon의 맨 앞 풍선을 꺼내 풍선의 번호와 종이에 적힌 수를 각각 r과 d에 할당한다. 결과값 리스트 res에 풍선의 번호를 추가하고, d에 따라 풍선을 이동한다. d가 양수이면 풍선들을 왼쪽으로 회전(-)시키는데 popleft로 풍선이 하나 줄었으므로 rotate에 -(d-1)을 인자로 넘긴다. d가 양수가 아니면(음수인 경우) 풍선들을 오른쪽으로 회전(+)시키기 위해 rotate에 -d를 인자로 넘긴다..