Search
Duplicate
🍭

[PS] 최고의 성과 달성을 위한 스케이트 연습

Created
2024/01/25 11:49
Tags
롤리팝쌤
그리디알고리즘
안녕하세요, 롤리팝입니다.
우리 선생님들은 이 추운 겨울을 어떻게 보내고 계실까요?
1.
방 안에서 따뜻한 장판의 유혹에 푹~
꽁꽁 언 겨울, 따스한 장판 위에서 뒹굴뒹굴! 외부 세계와의 소통을 잠시 끊고, 따끈따끈한 장판의 포근한 포옹에 몸을 맡기며 겨울 잠을 즐기시는 중.
책 한 권, 따뜻한 차 한 잔과 함께 하는 이 시간, 겨울의 진정한 낭만!
2.
이한치한! 추운 겨울도 열정적으로 밖에서 활동!
"추워도 우리는 멈추지 않아!"라고 외치고 눈 내리는 거리를 거닐거나 겨울 스포츠를 즐기며, 추운 날씨 속에서도 건강과 활력을 찾아요.
이한치한의 정신으로, 추위에 맞서 신나는 겨울을 즐기는 거죠!
저, 롤리팝은 마음 속으로는 '이한치한' 정신을 가득 품고 있어요. 마음은 마치 겨울철 활발한 야외 활
동을 즐기는 듯한 열정을 불태우고 있죠. 하지만 몸은... 따뜻한 장판의 유혹을 뿌리치지 못하고, 1번
선택지를 따르고 있답니다.
이번 레터에서 여러분과 함께 공유하고자 하는 PS 내용은 겨울의 대표적인 스포츠 스케이트에 관한
것 입니다. 학생들에게 컴퓨팅 사고력과 문제 해결 능력을 키우는 데 매우 유용한 '최적화 문제'를 담
고 있어요. 문제 내용을 살펴보면 스케이트장의 시작 지점, 중간 지점, 도착 지점에서 각각 최대한 빠
른 속도로 지나는 것을 목표로 하는데요. 어떻게 해결할 수 있을까요?

문제

28324번: 스케이트 연습
여러분은 주어진 스케이트 코스에서 스케이트를 연습하려고 한다. 이 코스는 시작 지점, $N$개의 중간 지점, 그리고 도착 지점으로 구성되어 있다. 이 연습은 시작 지점에서 $0$의 속력으로 출발하여, $1$번 중간 지점부터 $N$번 중간 지점까지 번호가 증가하는 순서대로 방문하고, $0$의 속력으로 도착 지점에 도달한 이후 종료된다.
https://www.acmicpc.net/problem/28324
여러분은 주어진 스케이트 코스에서 스케이트를 연습하려고 한다. 이 코스는 시작 지점, NN개의 중간
지점, 그리고 도착 지점으로 구성되어 있다. 이 연습은 시작 지점에서 0의 속력으로 출발하여, 1번
중간 지점부터 NN번 중간 지점까지 번호가 증가하는 순서대로 방문하고, 0의 속력으로 도착 지점에
도달한 이후 종료된다.
각 중간 지점에는 속력 제한 ViV_i가 있어, 다음으로 방문할 지점의 속력 제한을 초과하지 않도록 이동
하는 사이에 속력을 조절해야 한다. 속력을 높일 때는 원하는 만큼 높일 수 있지만, 속력을 낮추는 경
우에는 마지막으로 방문했던 지점에서의 속력에서 1만큼만 낮출 수 있다. 단, 출발 지점과 도착 지점
을 제외한 위치에서 속력은 0이 될 수 없다. 속력을 변경하지 않고 그대로 유지하는 것도 가능하다.
연습의 성과는 각 지점에서의 속력의 합과 같으므로 여러분은 이를 최대화하려고 한다. 스케이트 코스의 속력 제한이 주어졌을 때, 그 코스에서 얻을 수 있는 최대 연습의 성과를 구해보자. 예를 들어, 중간 지점이 3개인 코스의 속력 제한이 V=[2,3,1]V=[2,3,1]로 주어진 경우, 2번 중간 지점에서 3의 속력을 유지한다면 3번 중간 지점에서 1이하의 속력이 되도록 조절하는 것이 불가능하다.
이 코스에서 가능한 연습 방법 중 하나로, [2,2,1][2,2,1]의 순서대로 속력을 조절한다면 속력의 합은 2+2+12+2+1인 5가 된다. 다른 가능한 연습 방법으로 [1,1,1][1,1,1]과 [1,2,1][1,2,1]이 있지만, 이들의 속력의 합은 5를 초과하지 않는다. 따라서 이 코스에서 얻을 수 있는 가장 큰 연습의 성과는 5이다.
1. 입력
첫 번째 줄에 N N이 주어진다.
두 번째 줄에 V1,V2,…,VNV_1, V_2, … , V_N이 공백을 사이에 두고 차례대로 주어진다.
2. 출력
첫 번째 줄에 답을 출력한다.
3. 제한
•
주어지는 모든 수는 정수이다.
•
1≤N≤5000001≤N≤500000
•
1≤Vi≤1000000000(1≤i≤N)1≤V_i≤1000000000 (1≤i≤N)
4. 서브태스크
호
배점
제한
1
8
N≤8,Vi≤8(1≤i≤N)N≤8, V_i≤8 (1≤i≤N)
2
12
N≤500,Vi≤500(1≤i≤N)N≤500, V_i≤500 (1≤i≤N)
3
17
N≤5000,Vi≤5000(1≤i≤N)N≤5000, V_i≤5000 (1≤i≤N)
4
10
N≤5000N≤5000
5
53
추가 제약 조건 없음.
5. 예제 입력/출력 (1)
3 2 3 1
Plain Text
복사
출력
5
6. 예제 입력/출력 (2)
4 23 7 1 5
Plain Text
복사
출력
7
7. 출처
문제를 만든 사람: kdh9949,  kyo20111

롤리팝쌤과 문제 해결하기

그리디 알고리즘이란?
탐욕 알고리즘(Greedy algorithm)은 최적해를 구하는 데에 사용되는 근사적인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다. 순간마다 하는 선택은 그 순간에 대해 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적(전역적)인 해답을 만들었다고 해서 그것이 최적이라는 보장은 없다. 하지만 탐욕 알고리즘을 적용할 수 있는 문제들은 지역적으로 최적이면서 전역적으로 최적인 문제들이다. (출처: https://ko.wikipedia.org/wiki/탐욕_알고리즘)
스케이트장의 규칙 이해하기
•
시작 지점에서 속도는 0이에요.
•
중간 지점마다 속도 제한이 있어요. 예를 들어, 속도 제한이 3이라면 그 지점을 지날 때 속도는 3 이하여야 해요.
•
속도는 원하는 만큼 높일 수 있지만 낮출 때는 한 번에 1만큼만 낮출 수 있어요.
•
중간 지점에서는 속도가 0이 되면 안 돼요. 계속 움직여야 해요!
•
마지막으로 도착 지점에 도달할 때의 속도는 0이 되어야 해요.
아직도 규칙을 잘 모르시겠다고요?
규칙의 이해를 돕고자 예제 입력 1을 그래프로 그려보겠습니다. 아래 그래프는 스케이트 연습 문제의 해결 과정을 시각적으로 보여주며, 각 중간 지점(체크포인트)에서의 최적 속도를 보여주고 있습니다. 각 점 위의 텍스트는 해당 체크포인트의 속도 제한을 나타냅니다. 체크포인트 1에서는 최대 속도가 2, 체크포인트 2에서는 최대 속도가 2, 그리고 체크포인트 3에서는 최대 속도가 1로 설정되었습니다. 이렇게 각 지점에서의 최적 속도를 선택하여 총합을 최대화하는 것이 문제의 목표입니다.
전략 세우기
•
속도 조절: 다음 중간 지점의 속도 제한보다 빠르게 가고 있다면 속도를 조금씩 줄여야 해요. 하지만 너무 많이 줄이지는 마세요. 왜냐하면 다시 빠르게 갈 수 있도록 준비해야 하니까요!
•
최대한 빠르게: 각 지점을 최대한 빠른 속도로 지나가려고 해보세요. 이렇게 하면 더 많은 점수를 얻을 수 있어요.
힌트
•
마지막 지점에서 0의 속력으로 도착해야 하므로 마지막 지점에서 시작하여 각 지점의 최대 속도를 계산해 나가야 해요.
•
각 지점에서는 '이전 지점에서의 속도 + 1'과 '해당 지점의 속도 제한' 중 작은 값을 선택해야 해요.
문제 해결
N = int(input()) V = list(map(int, input().split())) # 마지막 지점에서의 속도를 0으로 설정 max_speed = 0 total_performance = 0 for i in range(N - 1, -1, -1): # 현재 지점의 속도 제한과 이전 지점의 최대 속도 중 작은 값 선택 max_speed = min(max_speed + 1, V[i]) total_performance += max_speed print(total_performance)
Python
복사
이제 우리는 파이썬을 사용하여 각 지점에서의 최적 속도를 계산하고, 이를 통해 전체 경로에서 최고의 성과를 얻을 수 있어요. 이 문제를 수업에 적용하신다면 학생들은 스케이트 연습을 통해 그리디 알고리즘을 이해하고, 컴퓨팅 사고력을 키울 수 있을 거예요.
우리 2024년에도 화이팅해요~!