[ BOJ 오답노트 ] 2775 파이썬 : 부녀회장이 될테야

2022 01 25

 

1. 틀린 기록

 

 

 

2. 원인 분석

- 이야 새로운 오답 결과!! 시간 초과다!!! 하하하하

- 이것이 바로 맞왜틀 (맞는데 왜 틀려)인가?

- 내가 시간 초과 낸 코드를 보면 다음과 같다.

- 층수와 호수의 최댓값이 14임에도 for문에 재귀함수 범벅을 해서... 시간 제한 1초를 넘어설 수밖에 없는 아주 드러운 코드였다!!

- 아이디어는 그대로하고 차라리 이중 for문으로 구현해야겠다고 생각했다. 그래봤자 14 X 14 = 196 번의 연산이므로..

 

 

 

3. 해결

- 다이나믹 프로그래밍을 생각했다. 그 중에서도 바텀업 방식으로 구현하고 이차원 리스트를 만들어서 메모이제이션을 구현하도록 했다.

- 어차피 1층 이상의 가구는 그 전 층의 사람 수들을 모두 계산해야 됐어서 바텀업 방식을 생각했다.

- 또한 한번 했던 연산을 또 연산하면 시간적인 낭비가 있을 것이라고 생각해서 메모이제이션을 생각했다.

 

 

 

4. 배운 점

- 일단 스스로 생각해서 동적 프로그래밍을 구현 해 본 것이 처음이라서 되게 신기했다.

- 생각보다 재귀 함수가 잡아먹는 시간이 꽤 크므로 최대한 사용하지 않는.. 혹은 불가피할 때에만 써야겠다고 생각했다.

- 메모이제이션으로 같은 연산을 두번 이상 하는 것을 방지하자.