[BOJ] 2775번: 부녀회장이 될테야

초보자의 마음으로 다시 시작하는 알고리즘 공부 🙂

 

문제

 

입출력 예시

어려운 문제는 아니지만 입출력 결과를 짚어보자.

 

1) 1 3 → 1층 3호에 사는 사람 수 구하기

1층 3호에 살려면 0층 1호~3호 사람을 다 데려와서 살아야 하고 0층은 각 호에 호실 번호만큼의 인원이 산다고 했기 때문에 1+2+3=6을 출력한다.

 

2) 2 3

1층 1호~3호 인원 총합 = 0층 1호+(0층 1호+0층 2호)+(0층 1호+0층 2호+0층 3호)=1+3+6=10

 

아이디어

1) 근본 = 0층

모든 k층 n호를 0층으로 표현하는 방법을 떠올렸는데 굳이 다 풀어서 계산할 필요가 있나 싶어서 패스

 

2) 규칙 찾기

수학&구현 파트는 규칙만 찾으면 생각보다 금방 풀리는 경우가 많아서 규칙을 찾아보려고 했지만 내가 내린 판단은? 규칙 없음!

 

3) 이전 층과의 관계 파악

단순무식한 방법으로 각 호실에 사는 사람 수를 쭉 적어봤고 'k층 n호 = k층 1호+(k-1)층 n호'라는 것을 발견했다.

 

풀이 초반에 k가 1일 때와 아닐 때를 나누는 방식도 생각해봤는데, 문제를 더 복잡하게 만드는 것 같아서 적용하지는 않았지만 이전 층과의 관계를 사용하면 굳이 k를 경우에 따라 나눌 필요가 없었다.

 

핵심 코드

for _ in range(floor):
    for idx in range(1, room):
        person[idx] += person[idx-1]

 

층이 바뀔 때마다 호실에 사는 사람의 인원 수도 같이 바뀌기 때문에 배열의 제일 마지막 원소를 출력해주면 된다.