백준 하모니[32338] 파이썬(Python) 코드 + 해설

백준 하모니 32338

 

백준 32338 하모니 문제는 Solved.ac기준 골드 1 문제입니다.

 

1. 문제 해설

한양이는 최대한 많은 기력을 얻고자 한다. 그는 수련의 조화 합이 0이 되면, 즉 양과 음이 균형을 이루면 총 기력이 두 배가 된다는 것을 알고 있다. 따라서, 각 수련을 선택하여 전체 시간 제한 내에서 최대의 기력을 얻는 것이 목표이다.

제한사항 분석:

• 수련의 수 T는 최대 100이다.
• 총 시간 N은 최대 1000이다.
• 각 수련의 시간 Wi​​는 최대 300이다.

따라서, 동적 계획법(DP)을 사용하여 문제를 해결할 수 있다.

2. 문제 해결 방법

2.1 DP 테이블 정의

• dp[time][harmony_sum] = 최대 기력
  • 여기서,
    • time: 현재까지 사용한 총 시간 (0 ≤ time ≤ N)
    • harmony_sum: 현재까지 선택한 수련들의 조화 합 (-T ≤ harmony_sum ≤ T)
    • dp[time][harmony_sum]: 해당 시간과 조화 합으로 얻을 수 있는 최대 기력
• 조화 합의 범위는 −T부터 T까지이며, 이를 인덱스로 사용하기 위해 shift를 적용한다. 즉, 실제 조화 합에 +T를 더하여 0부터 2T까지의 인덱스를 사용한다.

2.2 초기화

• 모든 dp 값을 −∞로 초기화한다.
• dp[0][T] = 0으로 설정한다. (조화 합 0에 해당하는 인덱스는 T이다.)

2.3 DP 점화식

• 각 수련에 대해 DP를 갱신한다.
• 시간과 조화 합의 인덱스를 올바르게 사용하도록 주의해야 한다.

2.4 결과 계산

• 모든 가능한 시간과 조화 합에 대해 최종 결과를 계산한다.
• 조화 합이 0인 경우, 총 기력을 두 배로 계산한다.
• 최대 기력을 얻을 수 있는 조화 합과 기력을 찾는다.
• 여러 개의 최대 기력이 존재하면, 조화 합의 절댓값이 작은 것을 선택한다.
• 조화 합의 절댓값까지 같다면, 양의 조화 합을 선택한다.

3. 백준 32338 하모니 파이썬(Python) 정답 코드

import sys
input = sys.stdin.readline

T, N = map(int, input().split())
practices = []
for _ in range(T):
    M_i, W_i, V_i = input().split()
    M_i = int(M_i)
    W_i = int(W_i)
    V_i = int(V_i)
    practices.append((M_i, W_i, V_i))

# DP 테이블 초기화
dp = [ [-float('inf')] * (2 * T + 1) for _ in range(N + 1) ]
offset = T  # 조화 합을 0부터 2T로 만들기 위한 오프셋
dp[0][offset] = 0  # 시간 0, 조화 합 0에서 기력 0

# DP 수행
for M_i, W_i, V_i in practices:
    for time in range(N, W_i - 1, -1):
        for harmony in range(-T, T + 1):
            prev_harmony = harmony - M_i
            if -T <= prev_harmony <= T:
                if dp[time - W_i][prev_harmony + offset] != -float('inf'):
                    new_value = dp[time - W_i][prev_harmony + offset] + V_i
                    if dp[time][harmony + offset] < new_value:
                        dp[time][harmony + offset] = new_value

# 결과 계산
max_energy = -float('inf')
best_harmony = None

for harmony in range(-T, T + 1):
    for time in range(N + 1):
        energy = dp[time][harmony + offset]
        if energy == -float('inf'):
            continue
        adjusted_energy = energy * 2 if harmony == 0 else energy
        if adjusted_energy > max_energy:
            max_energy = adjusted_energy
            best_harmony = harmony
        elif adjusted_energy == max_energy:
            if abs(harmony) < abs(best_harmony):
                best_harmony = harmony
            elif abs(harmony) == abs(best_harmony) and harmony > best_harmony:
                best_harmony = harmony

print(f"{best_harmony} {int(max_energy)}")

4. 백준 32338 하모니 파이썬(Python) 코드 설명

1. 입력 처리 및 초기화
   • 수련의 수 T와 총 시간 N을 입력받는다.
   • 각 수련에 대한 정보를 입력받아 practices 리스트에 저장한다.
   • DP 테이블 dp를 초기화한다.
     • 크기는 (N+1)×(2T+1)이다.
     • 조화 합의 범위는 −T부터 T이므로, 인덱스는 0부터 2T로 설정하고, 이를 위해 offset = T를 사용한다.
     • dp[0][offset] = 0으로 초기화한다.
2. DP 수행
   • 각 수련에 대해 다음을 수행한다.
     • 시간을 N부터 Wi ​까지 감소시키며 반복한다.
     • 조화 합을 −T부터 T까지 반복한다.
     • 이전 조화 합 prev_harmony = harmony - M_i를 계산한다.
     • prev_harmony가 −T이상 T 이하인 경우에만 DP를 갱신한다.
     • dp[time][harmony + offset] 값을 업데이트한다.
3. 결과 계산
   • 모든 가능한 시간과 조화 합에 대해 최대 기력을 계산한다.
   • 조화 합이 0인 경우 기력을 두 배로 계산한다.
   • 최대 기력 max_energy와 해당하는 조화 합 best_harmony를 업데이트한다.
   • 여러 최대 기력이 존재하면, 조화 합의 절댓값이 작은 것을 선택하고, 절댓값이 같다면 양의 조화 합을 선택한다.
4. 결과 출력
   • 최종적으로 best_harmony와 max_energy를 출력한다.

 

5. 백준 32338 하모니 제출 결과

백준 32338 하모니 제출 결과

 

도움이 되셨다면 공감과 댓글 부탁드립니다