[백준 25405] 2022년 정보 올림피아드 2차 "레벨 업"

문제 출처 : https://www.acmicpc.net/problem/25405

25405번: 레벨 업

이 문제는 2022년 정보올림피아드 2차 중등부 4번, 고등부 3번 문제로 출제되었습니다. 레벨의 균형을 맞춰가며 올리는 문제 입니다. 매번 트레이닝 할 때마다 레벨이 낮은 K개의 캐릭터의 레벨을 1씩 M번 올리면 해결 되는 간단한 문제 입니다. 문제는 캐릭터가 총 10만이고, K값의 최대값도 10만이며 올려야하는 레벨의 최대값은 10억이라는 것입니다. 따라서 일반적인 방법으로는 문제를 해결할 수 없습니다.

서브테스크 1

도저히 문제를 해결할 방법이 떠오르지 않는다면 서브태스크 1번이라도 해결하여 4점을 받아야 합니다. 서브테스크1은 N과 M이 1000으로 매번 정렬하여 레벨이 낮은 순서로 K명의 레벨은 1씩 올려주면 됩니다. 그럼 간단하게 서브테크스 1번을 해결하는 코드를 확인해 보겠습니다.

입력 받기

mii = lambda : map(int, input().split())

N = int(input())
level = list(mii())
M, K = mii()

캐릭터 N의 값과 캐릭터들의 레벨값, 그리고 레벨을 올릴 횟수 M과 레벨을 올릴 캐릭터의 수 K를 입력 받습니다.

레벨 올려주기

for _ in range(M):
    level.sort()
    for i in range(K):
        level[i] += 1

level.sort()
print(*level) 

for문을 M번 반복하여 레벨을 올려줍니다. 매 번 정렬을 한 뒤 처음부터 K개의 캐릭터의 레벨을 1씩 올려줍니다. 마지막 레벨을 올려준 뒤 정렬을 한 후 출력해 주면 됩니다.

서브테스크2

서브테스크 2번을 이해하는 것이 이 문제의 핵심 입니다. K는 1인 경우를 해결하고, 이어 K가 여러명일 때를 해결해 보겠습니다. 예제 2번을 예를 들어 보겠습니다. 7, 4, 2, 9의 레벨을 가지고 있는데 여기서 K가 1일 때 레벨 M을 10을 올리는 경우를 생각해 보겠습니다.

 

이렇게 7, 4, 2, 9를 정렬하면 2, 4, 7, 9로 나타낼 수 있습니다. 여기에 레벨 10을 올려야 합니다. K가 1이기 때문에 맨 앞의 캐릭터의 레벨을 올려 줍니다.

그냥 맨 앞의 캐릭터에 레벨 10을 올려주면 이와 같은 모습이 될 것입니다. 이는 우리가 원하는 형태가 아닙니다. 레벨을 올렸을 때 뒤의 캐릭터의 레벨을 확인해서 뒤가 더 작다면 레벨을 나누어 주어야 합니다. 앞의 캐릭터 레벨이 2 + 10으로 12이고, 뒤의 캐릭터 레벨이 4이기 때문에 총 합은 16이 되고, 2로 나누면 레벨을 8씩 가지게 됩니다.

이제 세번째 캐릭터의 레벨을 확인해 봅니다. 2개의 캐릭터의 레벨이 8이 되었지만 세 번째 캐릭터의 레벨이 7로 더 작습니다. 따라서 이제 3개의 캐릭터의 래벨의 평균을 만들어 주어야 합니다.

반응형

2개의 캐릭터까지의 레벨이 16이고, 뒤의 캐릭터의 레벨이 7이기 때문에 이 3개의 레벨 총 합은 16 + 7로 23이 됩니다. 이를 3으로 나누어 주면 7이되고 2가 남게 됩니다. 즉 3개의 캐릭터의 평균 높이는 7이되고 남은 2를 뒤쪽에 1씩 넘겨줍니다.

최종적으로 다음과 같은 모양이 됩니다. 그럼 이 과정을 코드로 확인해 보겠습니다.

입력 받기

입력 받는 부분은 서브테스크1의 입력받기와 같습니다. 여기서는 생략하도록 하겠습니다.

초기화 하기

level.sort()
K -= 1
right = K
tot_level = level[K] + M
cnt = 1

먼저 캐릭터의 레벨이 저장되어 있는 리스트 level을 정렬합니다. 맨 앞에 가장 낮은 레벨의 캐릭터가 오도록 합니다. 다음으로 캐릭터의 시작이 0번이기 때문에 K값에 1을 빼주었습니다. right값은 오른쪽을 확인하여 같이 평탄화해줄 끝 값이 됩니다. 처음에는 K와 같은 0이 됩니다.

tot_level은 올리고자 하는 레벨입니다. level[K]는 2이고, M은 10이기 때문에 tot_level은 12가 됩니다. cnt는 캐릭터를 카운트 해주는 값입니다. 처음에는 하나의 캐릭터만 있기 때문에 1입니다.

평탄화 하기

while True:    
    x = tot_level // cnt
    
    if right < N - 1 and level[right + 1] <= x:
        right += 1
        tot_level += level[right]
        cnt += 1
    else:
        break

tot_level // cnt 값인 x는 12 // 1로 12입니다. right값은 범위를 벗어나면 안되기 때문에 right < N - 1 의 범위안에 있어야 합니다. 그리고 level[right + 1]의 값을 확인합니다. right값은 0이기 때문에 level[1]의 값을 확인하는 것이고 그 값은 4입니다. 12는 4보다 크기 때문에 평탄화 작업이 필요합니다. right값을 1 늘려주고 평탄화할 값인 level[1]의 값을 더해줍니다. 그리고 cnt 값도 1 늘려줍니다.

반복문이 한 번 돌고 나면 tot_level은 16입니다. cnt값은 2입니다. 따라서 레벨업한 높이는 16 // 2로 8 입니다. 다음 레벨을 확인해보니 7로 8보다 작습니다. right값은 2가 되고, tot_level도 16에서 7을 더한 23이 됩니다. cnt 값도 3이 됩니다.

한 번 더 반복문이 돌고 x값은 23 // 3으로 7이 됩니다. 다음 level은 9로 x보다 크기 때문에 평탄화가 끝나고 반복문이 종료 됩니다.

출력하기

ans = []
for i in range(N):
    if i <= right - tot_level % cnt: 
        level_i = x
    elif i <= right:
        level_i = x + 1
    else:
        level_i = level[i]
    ans.append(level_i)

print(*ans)     

ans에 레벨 정보를 담을 것입니다. 평탄화를 통해 레벨이 23 // 3으로 7이 되었지만 나누어 떨어지지 않고 나머지가 있습니다. 23 % 3인 2명의 캐릭터는 1씩 더 올려주어야 합니다. right값인 2에 나머지 2를 빼준 0번째 까지는 7이 되고, 그 뒤로 right까지는 7 + 1이 되고, right 이후는 값의 변화가 없습니다. 따라서 그냥 원래 값을 저장합니다. 최종적으로 ans를 출력하면 됩니다.

전체 코드

서브 테스크 2의 전체 코드를 확인해 보겠습니다.

mii = lambda : map(int, input().split())
N = int(input())
level = list(mii())
M, K = mii()

level.sort()
K -= 1
right = K
tot_level = level[K] + M
cnt = 1

while True:    
    x = tot_level // cnt
    
    if right < N - 1 and level[right + 1] <= x:
        right += 1
        tot_level += level[right]
        cnt += 1
    else:
        break
    
ans = []
for i in range(N):
    if i <= right - tot_level % cnt: 
        level_i = x
    elif i <= right:
        level_i = x + 1
    else:
        level_i = level[i]
    ans.append(level_i)

print(*ans)

서브테스크4

다음으로 서브테스트 3을 건너뛰고 서브테스트4를 알아보겠습니다. 서브테스크 4가 해결되면 자연스럽게 서브테스크 3도 해결되기 때문입니다.

서브테스크2를 통해 오른쪽에 높은 레벨이 있을 경우 평탄화를 어떻게 해야하는지 알아보았습니다. K값이 1보다 큰 경우는 오른쪽 뿐만 아니라 왼쪽도 신경써야 합니다. 예를 들어 다음과 같은 레벨이 있다고 하겠습니다.

여기에 레벨을 올릴 캐릭터 K는 3, 올릴 레벨 M은 5라고 하겠습니다. 그냥 앞에서의 캐릭터 3개에 레벨을 7씩 올려 보겠습니다.

K가 1일때와 똑같이 K값이 3인 부분부터 시작해 보겠습니다. 3번째 레벨은 7 + 4로 11이고 오른쪽 레벨 7보다 크기 때문에 K가 1일때와 똑같이 평탄화 작업을 합니다.

다음과 같은 모양이 되고 오른쪽은 평탄화가 되었습니다. 이제 왼쪽을 봐야 합니다. 왼쪽인 2번째의 레벨이 7 + 4인 11로 3번째인 9보다 큽니다. 왼쪽도 오른쪽과 마찬가지로 더해주어 평탄화 작업을 하면 됩니다.

맨 앞인 level[0]은 7 + 1인 8로 level[1]보다 작기 때문에 평탄화 대상이 되지 않습니다.

알고리즘 이해하기

이제 우리는 정렬을 통해 총 3개의 그룹으로 나눌 수 있습니다.

1. M만큼 레벨이 올라가는 그룹
2. x, x + 1 레벨이 번갈아가며 평탄화되는 그룹
3. 레벨이 올라가지 않는 그룹

이렇게 2번 그룹의 평탄화를 진행하면 1번 그룹과 3번 그룹의 경계를 알 수 있습니다. 그 경계를 통해 어떤 레벨을 올릴 것인지 확인하면 됩니다.

앞서 서브테스크2에서 오른쪽을 해결하였기 때문에 왼쪽 부분만 추가하는 방식으로 코드를 작성해 보겠습니다.

입력 받기

앞서 입력 받는 부분과 같습니다.

초기화 하기

level.sort()
K -= 1
left = K
right = K
tot_level = level[K] + M
cnt = 1

초기화 부분도 서브테스트2와 똑같습니다. 다만 여기에는 left 변수가 추가되었습니다. left 역시 처음에는 K값과 같습니다.

평탄화 하기

while True:
    x = tot_level // cnt

    if 0 < left and x < level[left - 1] + M:
        left -= 1
        tot_level += level[left] + M
    elif right < N - 1 and level[right + 1] <= x:
        right += 1
        tot_level += level[right]
    else:
        break

    cnt += 1

기존 서브테스크2의 로직에 왼쪽에 대한 로직이 추가 되었습니다. left값은 0보다 커야하고, x보다 level[left - 1] + M 한 값이 클 때 작동합니다. left값을 1 줄여주고, 해당 레벨을 더해줍니다. 오른쪽과 차이점이라면 level[left]만 더해주는 것이 아니라 올려주는 M값도 추가적으로 더해주어야 합니다.

오른쪽, 왼쪽 모두 cnt 값이 더해지기 때문에 if문 바깥으로 빼주었습니다.

출력하기

ans = []
for i in range(N):
    if i < left:
        level_i = level[i] + M
    elif i <= right - tot_level % cnt:
        level_i = x
    elif i <= right: 
        level_i = x + 1
    else:
        level_i = level[i]
    ans.append(level_i)

print(*ans)

출력부분 역시 서브테스크2에 앞부분을 추가해 주었습니다. left보다 작은 i값은 평탄화 대상이 아니기 때문에 그냥 M을 더해주면 됩니다. 그 외 로직은 서브테스크2와 똑같습니다.

전체코드

전체 코드를 확인해 보겠습니다.

mii = lambda : map(int, input().split())
N = int(input())
level = list(mii())
M, K = mii()

level.sort()
K -= 1
left = K
right = K
tot_level = level[K] + M
cnt = 1

while True:
    x = tot_level // cnt

    if 0 < left and x < level[left - 1] + M:
        left -= 1
        tot_level += level[left] + M
    elif right < N - 1 and level[right + 1] <= x:
        right += 1
        tot_level += level[right]
    else:
        break

    cnt += 1

ans = []
for i in range(N):
    if i < left:
        level_i = level[i] + M
    elif i <= right - tot_level % cnt:
        level_i = x
    elif i <= right: 
        level_i = x + 1
    else:
        level_i = level[i]
    ans.append(level_i)

print(*ans)