[python] 백준 28324. 스케이트 연습

문제

https://www.acmicpc.net/problem/28324

여러분은 주어진 스케이트 코스에서 스케이트를 연습하려고 한다. 이 코스는 시작 지점, N개의 중간 지점, 그리고 도착 지점으로 구성되어 있다. 이 연습은 시작 지점에서 0의 속력으로 출발하여, 1번 중간 지점부터 N번 중간 지점까지 번호가 증가하는 순서대로 방문하고, 0의 속력으로 도착 지점에 도달한 이후 종료된다.

 

각 중간 지점에는 속력 제한 Vi가 있어, 다음으로 방문할 지점의 속력 제한을 초과하지 않도록 이동하는 사이에 속력을 조절해야 한다. 속력을 높일 때는 원하는 만큼 높일 수 있지만, 속력을 낮추는 경우에는 마지막으로 방문했던 지점에서의 속력에서 1만큼만 낮출 수 있다. 단, 출발 지점과 도착 지점을 제외한 위치에서 속력은 0이 될 수 없다. 속력을 변경하지 않고 그대로 유지하는 것도 가능하다.

 

연습의 성과는 각 지점에서의 속력의 합과 같으므로 여러분은 이를 최대화하려고 한다. 스케이트 코스의 속력 제한이 주어졌을 때, 그 코스에서 얻을 수 있는 최대 연습의 성과를 구해보자.

 

예를 들어, 중간 지점이 3개인 코스의 속력 제한이 V=[2,3,1]=로 주어진 경우, 2=번 중간 지점에서 3의 속력을 유지한다면 3번 중간 지점에서 1이하의 속력이 되도록 조절하는 것이 불가능하다. 이 코스에서 가능한 연습 방법 중 하나로, [2,2,1]의 순서대로 속력을 조절한다면 속력의 합은 2+2+1인 5가 된다. 다른 가능한 연습 방법으로 [1,1,1]과 [1,2,1]이 있지만, 이들의 속력의 합은 5를 초과하지 않는다. 따라서 이 코스에서 얻을 수 있는 가장 큰 연습의 성과는 5이다.

입력

첫 번째 줄에 N이 주어진다.

두 번째 줄에 V1,V2,…,Vn이 공백을 사이에 두고 차례대로 주어진다.

출력

첫 번째 줄에 답을 출력한다.

제한

• 주어지는 모든 수는 정수이다.
•  1≤N≤500000 
•  1≤Vi≤1000000000 (1≤i≤N)

서브태스크

---

풀이

쉽지 않았다... 처음에 감을 아예 잘못 잡았던 게 컸던 것 같다. 뭐랄까... 한 번 이렇게 풀면 되겠다하고 쓴 코드에서 크게 벗어나지 못하는게 가장 큰 문제였다. 조금 천천히 생각했다면, 금방 아이디어를 찾을 수 있는 문제였다. 헤맸던 건.. 뒤에 시행착오 파트에서 설명하고 다시 새로 풀면서 짰고 맞았던 걸 이야기해보겠다.

 

일단 가장 먼저 떠올려야하는 특징은 이거다.

이후의 최소값에서 +1된 값 혹은 해당 중간지점에 제한속도 값. 둘 중 작은 값이 들어간다는 것이다.

이후의 최소값을 구하기가 어려운 것이라면, 그걸 이전 값으로 만들어버리면 그만이다. 즉, Vi값을 받은 v 배열을 역순으로 바꿔서 위 특징을 코드에 녹여내면 된다.

import sys

n = int(sys.stdin.readline().strip())
v = sys.stdin.readline().split()
v.reverse()
sum = 0
a = 0

for i in range(n):
    if i == 0: #0이 되기 전, 즉 마지막 전에는 무조건적으로 1이 되어야 한다.
        a = 1
        sum += 1
    else: #이전에 구한 최소값에서 1을 더한 값 혹은 해당 중간 지점에
        a = min(a+1, int(v[i]))# 제한속도 중 작은 값을 변수 a에 넣어준다
        sum += a

print(sum)

 

이렇게 풀어서 맞았다! 배열을 역순으로 바꾸는 것과 이전 값에 1씩 더한다는 아이디어만 금방 생각해낸다면, 금방 풀 수 있었던 문제였다고 생각한다.

 

---

시행착오

자... 그럼 이제 어떤 식으로 헤맸는지..이야기를 해보자면....

일단 배열을 역순으로 바꿔야겠다는 생각을 하지 못했다. 그래서 for문을 돌려서 이후 지점들의 제한속도들에 이후 지점들이 현재 내가 가리키는 지점과의 거리를 계산해서 합해주는 방식으로 생각했다. 말로만 해도 못알아듣겠다... 나도 사실 내가 짠 코드인데... 사실 설명하자하면 좀 어버버된다. 그만큼 잘못짠 코드라는 것.

import sys

n = int(sys.stdin.readline().strip())
v = sys.stdin.readline().split()
sum = 0
v[n-1] = 1 #마지막 직전 중간지점에서는 무조건 1이어야 하므로 이를 계산할때 헷갈리게 하지 않기 위해 추가했다.

for i in range(n):
    if i != n-1: #마지막 직전 지점이 아니라면
        m = int(v[i]) #m이라는 변수에 현재 지점의 제한 속도를 넣어주고
        for j in range(n-i):#for문으로 현재 지점에서 j만큼 떨어진 지점의 제한속도 + j만큼의 거리
            if m > int(v[i+j])+j:#만약 위 j만큼의 거리+j만큼 떨어진 지점의 제한속도가 현재의 제한속도보다 작다면
                m = int(v[i+j])+j #해당하는 값을 m에 넣어주고 이를 반복해서 j가 마지막 지점까지 가서 계산하도록
        sum += m #그렇게 최종적으로 구한 값을 sum에 더해준다
    else: #마지막 직전 중간지점에서는 무조건 1이어야 하므로
        sum+=1

print(sum)

 

결론적으로는 20점이 나왔다. n이나 v가 500 이하일때는 해당 코드가 가능하지만, 그 이상으로 커진다면 계산이 틀리게 나온다는 뜻인 것 같다. 어떠한 코드의 문제로 이렇게 된지는 모르겠지만, 일단 시간 초과 문제일 수도 있다고 생각해서 코드를 새로 짜는 게 낫다고 생각했다.

 

기존에 짜놓은 코드와 생각이 있다보니까, 아예 새로운 아이디어를 찾아내기가 쉽지 않았다. 말로, 손으로 몇 번 더 끄적이고 다른 그리디 알고리즘 문제를 풀어보고 나서야 겨우 해결할 수 있었다.

 

그러니... 내가 하고 싶은 말이 뭐냐면... 이전에 풀었던 방식이 틀린 것 같다면 미련을 남기지 말고 새로운 방식을 빠르게 생각해내는 버릇을 들여야겠다... 뭐 그런 말이다!

 

+) 추가적으로 왜.. 20점일까.. 시간초과가 맞을까 확인을 위해 chat gpt에 도움을 받았다. 음... 역시나 시간복잡도 문제라고 답한다. 결과적으로 시간이 무한정이라면 풀리는 코드이긴 했던 거다. 단지 너무 많은 반복문으로... 시간이 너무 오래 걸릴 뿐이었던 거지... 결과적으로 이 아이디어도 완전히 틀린 건 아니라서 조금 기분이 좋아졌다. 

하여튼 꼬아서 풀지 말자~