[SWEA] 수영장 (모의 SW 역량테스트) / python

1. 문제 설명

김 프로는 수영장을 이용한다.
김 프로는 지출이 너무 많아 내년 1년 동안 각 달의 이용 계획을 수립하고 가장 적은 비용으로 수영장을 이용할 수 있는 방법을 찾고 있다.
수영장에서 판매하고 있는 이용권은 아래와 같이 4 종류이다.  
① 1일 이용권 : 1일 이용이 가능하다.  
② 1달 이용권 : 1달 동안 이용이 가능하다. 1달 이용권은 매달 1일부터 시작한다.  
③ 3달 이용권 : 연속된 3달 동안 이용이 가능하다. 3달 이용권은 매달 1일부터 시작한다.       
(11월, 12월에도 3달 이용권을 사용할 수 있다 / 다음 해의 이용권만을 구매할 수 있기 때문에 3달 이용권은 11월, 12월, 1윌 이나 12월, 1월, 2월 동안 사용하도록 구매할 수는 없다.)  
④ 1년 이용권 : 1년 동안 이용이 가능하다.
1년 이용권은 매년 1월 1일부터 시작한다.

 

이용 계획에 나타나는 숫자는 해당 달에 수영장을 이용할 날의 수를 의미한다.

각 이용권의 요금과 각 달의 이용 계획이 입력으로 주어질 때, 가장 적은 비용으로 수영장을 이용할 수 있는 방법을 찾고
그 비용을 정답으로 출력하는 프로그램을 작성하라.

 

[입력]

입력의 맨 첫 줄에는 총 테스트 케이스의 개수 T가 주어지고, 그 다음 줄부터 T개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 1일 이용권의 요금, 1달 이용권의 요금, 3달 이용권의 요금, 1년 이용권의 요금이 순서대로 한 칸씩 띄고 주어진다.

그 다음 줄에는 1월부터 12월까지의 이용 계획이 주어진다.

 

[출력]

테스트 케이스 개수만큼 T개의 줄에 각각의 테스트 케이스에 대한 답을 출력한다.

각 줄은 "#t"로 시작하고 공백을 하나 둔 다음 정답을 출력한다. (t는 1부터 시작하는 테스트 케이스의 번호이다)

출력해야 할 정답은 이용 계획대로 수영장을 이용하는 경우 중 가장 적게 지출하는 비용이다.

 

2. 풀이 전 계획과 생각

• 테스트 케이스의 수 → test_case_num
• 이용권의 가격들 → 1차원 배열 → ticket_prices[]
• 12개월 이용계획 → 1차원 배열 → plan[]

 

언제 어떤 이용권을 선택하는 것이 적은 비용인지 알 수 없음으로 모든 경우를 다 따져줘야 한다.

(이용권의 대소관계도 정해져 있지 않다.)

모든 경우의 수를 다 따져보면 12^4 = 20731이다. 완전탐색이 가능하다.

나올 수 있는 모든 경우를 다 따져보자.

비용을 계산하고 비용 다 계산할 때마다 최소 비용을 갱신한다.

• 초기화하는 함수
  • 이용권 가격들 → 1차원 배열
  • 12개월 이용 계획 → 앞에 0을 붙인다. 1차원 배열
• 필요한 변수
  • choose_ticket = []
    • 선택한 ticket이 무엇인지 나타내는 배열 (선택 안 함 : 0 / 1일 이용권 : 1 / 1달 이용권 : 2 / 3달 이용권 : 3 / 1년 이용권 : 4)
• 경우의 수를 다 만들어주는 함수
  • 0이 아닌 월마다 어떤 이용권을 쓸 것인지 넣는다.
  • go(curr_month) : 해당 월마다 이용권을 선택하는 함수
    • choose(month + 1)
    • choose(month + 3)
  • 종료 조건 : month ≥ 12
  • 예외 조건 : month 13, 14, 15
• 비용 계산하는 함수
  • 이용권 선택에 따른 비용 계산 → 선택한 ticket이 무엇인지

⇒ 가장 적은 비용 출력한다.

 

3. 풀이하면서 막혔던 점과 고민

🤔 3달 연속일 때 선택 안 함을 추가할 수 있는데 위의 처리를 어떻게 할까?

0으로 초기화

curr_num + 3하면 된다.

 

🤔 1일 처리랑 1년 처리는 어떻게 또 해줄 수 있을까?

go(month + 1, cost + price[0] * 해당 월의 계획 일)

go(month + 12, price[3])

⇒ 이용권 선택 여부를 전역변수로 두어 이용권을 선택하여 비용 계산 해주기 보다는
모든 경우를 쉽게 계산하기 위해 계산도 파라미터에 넣어주자.
왜냐하면 각 월마다 다 이용권이 필요한 것이 아니기에,
이용권이 필요없는 월에는 이용권이 없는지, 이용권이 필요있는 월에는 이용권이 있는지,
(3개월마다 처리하면 필요없는 예외 경우가 발생하여 일일히 처리해야 한다) 월을 계속 확인해줘야 하기 때문이다.

 

최종 설계

• 초기화하는 함수
  • 이용권 가격들 → 1차원 배열 (ticket_price)
  • 12개월 이용 계획 → 앞에 0을 붙인 1차원 배열 (month)
• 경우의 수를 다 만들어주는 함수
  • go(curr_month, cost) : 해당 월마다 이용권을 선택하는 함수
    • plans에 날짜가 0이라면 다음달로 이동한다.
    • 그외
      • go(month + 1, cost + price[0] * 해당 월의 계획일 수)
      • go(month + 1, cost + price[1])
      • go(month + 3, cost + price[2])
      • go(month + 12, cost + price[3])
  • 종료 조건 : month > 12
    • min_pay 갱신한다.

⇒ 가장 적은 비용 출력한다.

 

4. 1차 풀이 (BackTracking)

def go(month, cost):
    global min_pay
    if month > 12:
        min_pay = min(min_pay, cost)
        return min_pay

    if plans[month] == 0:
        go(month + 1, cost)
        
    go(month + 1, cost + price[0] * plans[month])
    go(month + 1, cost + price[1])
    go(month + 3, cost + price[2])
    go(month + 12, cost + price[3])

def init():
    price = list(map(int, input().split()))
    plans = [0] + list(map(int, input().split()))
    return price, plans

test_case_num = int(input())

for simulation_count in range(1, test_case_num + 1):
    min_pay = 3000 * 31 * 12
    price, plans = init()
    answer = go(1, 0)
    print(answer)

문제점

• 틀렸습니다.
  ⇒ output이 None이 나온다. 전역변수를 함수에서 리턴하고 출력하면 None이 나온다.

 

5. 2차 풀이 (BackTracking)

• 함수를 리턴하지말고, 전역변수를 출력해주자.

def go(month, cost):
    global min_pay
    if month > 12:
        min_pay = min(min_pay, cost)
        return

    if plans[month] == 0:
        go(month + 1, cost)
    go(month + 1, cost + price[0] * plans[month])
    go(month + 1, cost + price[1])
    go(month + 3, cost + price[2])
    go(month + 12, cost + price[3])

def init():
    price = list(map(int, input().split()))
    plans = [0] + list(map(int, input().split()))
    return price, plans

test_case_num = int(input())

for simulation_count in range(1, test_case_num + 1):
    price, plans = init()
    min_pay = 3000 * 31 * 12
    go(1, 0)
    print("#" + str(simulation_count) + " " + str(min_pay))

 

6. 다른 풀이 (Dynamic Programming)

• 위의 문제는 DP로도 풀 수 있다.
  다음 비용을 추가하기 위한 조건이 간단하고,
  앞에 있는 전체 비용들을 다시 참고할 필요가 없기 때문이다.
  
  • 구하고자 하는 것 : 12월까지의 최종 비용 → dp[12]
  • 풀고자 하는 문제 : dp[N] = N월 되었을 때, 최종 비용
  • 점화식 :
    dp[N] = min( dp[N-1] + price[0] * plans[N-1],
                             dp[N-1] + price[1],
                            dp[N-3] + price[2],
                            dp[N-12] + price[3])
  • base_case : dp[0] = 0, dp 배열들을 0으로 초기화 한다.

def init():
    price = list(map(int, input().split()))
    plans = [0] + list(map(int, input().split()))
    return price, plans


def simulate():
    global min_pay
    dp = [0] * (12 + 1)

    for i in range(1, 12 + 1):
        dp[i] = min(dp[i-1] + price[0] * plans[i], dp[i-1] + price[1])
        if i >= 3:
            dp[i] = min(dp[i], dp[i-3] + price[2])
        if i >= 12:
            dp[i] = min(dp[i], dp[i-12] + price[3])

    min_pay = min(dp[12], min_pay)
    return


T = int(input())
for test_case in range(1, T + 1):
    price, plans = init()
    min_pay = 3000 * 31 * 12
    simulate()
    print("#" + str(test_case) + " " + str(min_pay))

 

7. 풀이 후 알게된 개념과 소감

• 전역변수를 함수에서 리턴하고 출력하면 None이 나오니, 전역변수를 출력하자.