백준 2775 - 부녀회장이 될테야(JAVA)

2775번: 부녀회장이 될테야 (acmicpc.net)

2775번: 부녀회장이 될테야

 

이번주 study에서 정한 5번째 문제를 풀어보았다. 이 문제는 문제상으로 보면 엄청 간단한데 뭔가 자꾸 읽다보면 재귀를 쓰는 건가 하는 느낌도 든다. 일단 가장 먼저 떠오른건 k층 n호라는 걸 이차원 배열로 나타내면 어떨까? 하는 것이었다.

 

알고리즘을 구할 때 단순히 머릿속으로만 생각하면 도저히 답이 안나와서 입력 예시 뿐만 아니라 다른 예시들까지도 적어보면서 풀어보았다.

 

ex) 1층 3호

0층 1호 + 0층 2호 + 0층 3호 = 1층 2호 + 0층 3호

 

ex2) 2층 3호

1층 1호 + 1층 2호 + 1층 3호 = 2층 2호 + 1층 3호

 

ex3) 1층 5호

0층 1호 + 0층 2호 + 0층 3호 + 0층 4호 + 0층 5호 = 1층 4호 + 0층 5호

 

자 지금 까지 들었던 3가지 예시들을 미지수로 표현해 보자.

 

k층 n호 = k층 n-1호 + k-1층 n호  이렇게 단순하게 표현할 수 있었다.

 

이까지 표현할 수 있었다면 그 다음부터는 문제의 조건을 잘 파악하면 해결이 끝난다.

1. 1 ≤ k, n ≤ 14 이므로 이차원 배열을 표현하는 for문은 2중 for문 형태를 띄고 있어야 한다.

2. k와 n으로 이루어질 이차원 배열의 크기는 15 이어야 한다.

3. k-1층과 n-1호가 발생하기 때문에 for문의 크기를 1부터 잡아주어야 Index 오류가 발생하지 않는다.

4. 마지막 출력이 한 번에 이루어져야 하므로 StringBuilder로 append하는 방식을 택한다.

5. 0층은 호수 번호만큼 사람이 있고, 1호는 항상 1명이 있다는 것을 염두한다.

 

 

이렇게 해결할 수 있었다. 알고리즘을 그대로 따라가면서 문제를 구현하면 위와 같이 간단한 이차원 배열 형태로 문제를 해결할 수 있었다. 이 문제의 핵심은 머리 보다 손이 규칙 찾는데에는 훨씬 뛰어난 방법이라는 것을 알아차리는 것이다.