SWExpertacademy 1952. [모의 SW 역량테스트] 수영장

목표: SWExpertacademy 1952. [모의 SW 역량테스트] 수영장 문제 풀기

환경: mac OS High Sierra 10.13.4, CLion

이 문제 또한 완전탐색으로 풀려고 합니다. 완전탐색이란 문제의 답을 찾는 것인데, 가능한 경우를 모두 나열하고, 각각이 해가 될 수 있는지 확인하는 방법입니다.

우선 완전탐색의 장단점을 얘기해보자면 장점으로는 어떻게든 답을 구해낼 수 있다는 것이에요. 모든 경우를 다 살펴보고 해를 구하는 것이니까요.

이 문제를 통해 알게된 것은 시간복잡도를 계산해보는 습관이 중요하다는 것입니다. 시간 안에 정확히 동작한다면, 그 방법은 좋은 방법입니다.

물론 더 빠른 방법으로 구현할 수 있으면 그게 최고겠죠.

[제약 사항]

  1. 시간 제한 : 최대 50개 테스트 케이스를 모두 통과하는 데 C/C++/Java 모두 3초

  2. 모든 종류의 이용권 요금은 10 이상 3,000 이하의 정수이다.

  3. 각 달의 이용 계획은 각 달의 마지막 일자보다 크지 않다.

수영장 이용 요금의 최소값을 구하는 문제입니다.

문제를 보자마자 파악해낸 것은 인간의 논리로 계산하는 것(그리디 알고리즘)보다

빠른 연산을 이용한 완전탐색이 답을 찾는데 안전한 방법이다. 라고 생각했습니다.

그래서 경우의 수를 나눠봤습니다.

1일 이용권을 사용하는 경우

1달 이용권을 사용하는 경우

3달 이용권을 사용하는 경우

1년 이용권을 사용하는 경우로 나뉘는데요.

처음 설계한 방법은 10월이전에만 3달 이용권을 사용하게끔 if문을 넣어줬었고, 1월달에만 1년치 이용권을 사용하게 하였습니다.

테스트케이스의 답과 다르게 나와서 뭐가 잘못되었는지 생각해봤습니다.

문제의 조건을 보면

① 1일 이용권 : 1일 이용이 가능하다.

② 1달 이용권 : 1달 동안 이용이 가능하다. 1달 이용권은 매달 1일부터 시작한다.

③ 3달 이용권 : 3달 동안 이용이 가능하다. 3달 이용권은 매달 1일부터 시작한다. (11월, 12월에도 3달 이용권을 사용할 수 있다)

④ 1년 이용권 : 1년 동안 이용이 가능하다. 1년 이용권은 매년 1월 1일부터 시작한다.

11월 12월 에도 3달 이용권을 사용할 수 있다고 친절하게 설명을 해줬습니다.

<이 말은 어느달이든 상관없이 3달 이용권과 1년 이용권을 사용해도 된다.>라는 인사이트를 주었습니다. 왜냐하면 어차피 최소값을 구하는게 답이기 때문에 넘치게 이용권을 남발한경우는 값을 최소값 갱신 if문을 통과하지 못할겁니다.

시간복잡도를 계산해보면 1월부터 12월까지 다 이용한다고 치면, 매 달마다 1일치 이용권을 사용하는 경우 1달치 이용권을 사용하는 경우 .. 총 네가지 방법이 가능합니다.

그러므로 4번 * 4번 * .. * 4번, 총 4^12번 이 가능하고 O(2^12) 약 1600만이라는 시간복잡도가 나옵니다.

1초에 1억번 연산한다고 가정하였을때 1초에 수행이 된다는 것을 알 수 있습니다.

이 문제를 풀기 위한 사전 문제풀이는 알파벳 암호만들기 1+2+3더하기 등 재귀를 통한 해결할 수 있는 조합적문제들 입니다.

수영장

[code] ( https://github.com/yobs0814/problemSolving/blob/master/SWExpert/P1952/main.cpp )