[알고리즘] 부녀회장이 될테야 - DP

문제 링크

 

부녀회장이 될테야 : https://www.acmicpc.net/problem/2775

 

문제탐색

기본 원리 탐색

• "a층b호에 살려면 a-1층 1호~b호까지 사람들의 수의 합만큼 사람들을 데려와 살아야한다" 라는 규칙에 따라 수를 나열 한 후 k층 n호에는 몇명이 사는지 구하는 문제이다.
• 기본적으로 0층은 1, 2, 3, 4, 5 ... 이런식으로 나열되며 그에따라 1층은 1, 3, 6, 10 ....순으로 나열될 것이다.

 

시간복잡도와 알고리즘

• 시간제한 : 0.5초
  • 약 5천만 번의 연산이 가능하다고 가정합니다.
• 최대 층,호 : 14  

해당 문제의 경우 k층 n호의 거주민수가 어떻게 계산되는지 파악하는것이 우선입니다.

각 층,호 의 주민 수를 2차원 리스트에 담았다는 가정하에, k층  n호의 거주민 수 를

파이썬 코드 식으로 표기하면 다음과 같습니다.

 

k층 n호 거주민 수 =  k-1층 n호까지 모든 거주민수 합 =  sum(list[k-1][:n])

 

k층 n호 계산식에 따라 모든 집의 거주민수를 구한다고 한다면, 

호에 대한 계산N회를 모든 호에 대하여N회 진행하고 이것을 모든 층에대하여 K회 해야하므로

O(N*N*K)=14*14*14=2744회 가 됩니다.

위 과정대로 구현하여도 시간복잡도에 영향은 없다고 할 수 있습니다.

 

=> 따라서 위 점화식 바탕으로 14층 14호까지 모든 집 거주민 수를 구한 다음 답을찾게끔 DP알고리즘을 적용합니다. 

 

코드설계하기

1. 테스트 케이스를 리스트로 입력 받습니다.
2. 0층 거주민(1,2,3,4,5....14)을 14호 까지만 포함한 2차원 리스트를 선언합니다.
3. n호의 거주민수 = sum(list[1-1][:n]) 을 적용하여 1층의 14호까지 거주민수를 구합니다.
4. 14층까지 3. 과 같은 원리로 반복합니다.
5. 만들어진 2차원 리스트를 활용하여 테스트 케이스를 순회하며 k행 n열 거주민수를 출력합니다.

 

시도회차 수정사항

 

정답코드

import sys
T=int(sys.stdin.readline())
target=[]

for x in range(T): #테스트 케이스 입력
    k=int(sys.stdin.readline())
    n=int(sys.stdin.readline())
    target.append([k,n])

layer=[[1,2,3,4,5,6,7,8,9,10,11,12,13,14]] #아파트 건설 (0층 미리 선언)
 
for k in range(14): # 14층 14호까지 모든 거주민수 계산
    addLayer=[]  # 아파트에 추가할 1개층의 호 리스트
    for n in range(14):# 각 호 거주민수 계산 후 리스트에 추가
        addLayer.append(sum(layer[k][:n+1])) # n호 거주민수 =  k층 n호까지 거주민수 합
    
    layer.append(addLayer) # 1개층 호 리스트를 아파트에 추가


for x in target:#테스트케이스 순회
    print(layer[x[0]][x[1]-1]) # 호는 1호 부터 시작이므로 -1