[BOJ] 백준 32867번 Python

백준 32867번 Python

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

 

문제

---

컴스 최고의 피아니스트 예원이는 오른손만으로도 모든 곡을 연주할 수 있다.

비결은 손을 최대한 조금 움직이는 것이다.

예원이가 연주하는 피아노에는 200000개의 흰건반만 있으며,

가장 왼쪽 건반부터 순서대로 1, 2, …, 200000까지의 번호가 차례대로 매겨져 있다.

예원이의 손 길이는 한 건반 K개만큼이며,

다음에 치려는 건반이 손 안에 있다면 손을 움직이지 않고 다음 음을 낼 수 있다.

예를 들어, 손 길이가 건반 5개만큼이고 오른손 엄지를 1번 건반에 두었다면 1번 건반부터 5번 건반까지는 손을 움직이지 않고 칠 수 있지만, 이 범위를 벗어나는 건반을 누르려면 손을 다른 위치로 움직여야 한다.

다음 곡을 연주하려면 N개의 흰건반을 순서대로 눌러야 한다.

예원이는 원하는 위치에 손을 두고 연주를 시작하며, 연주 중 필요할 때만 손을 움직일 것이다.

하지만 예원이는 수많은 과제에 시달리느라 악보를 분석할 시간이 없다.

바쁜 예원이를 대신 곡을 연주하기 위해 손을 옮겨야 하는 최소 횟수를 구하는 프로그램을 작성해 주자!

 

 

입력

---

첫째 줄에 두 정수 N, K가 공백으로 구분되어 주어진다. (1 ≤ N ≤ 200000; 1 ≤ K ≤ 1000)

둘째 줄에는 눌러야 하는 건반의 번호 a1, a2, …, aN이 공백으로 구분되어 주어진다.

이는 i번째로 누르는 건반이 a_i번 건반이라는 의미이다. (1 ≤ a_i ≤ 200000)

 

 

출력

---

첫째 줄에 손을 옮겨야 하는 최소 횟수를 출력한다.

 

반응형

풀이

---

import sys
input = sys.stdin.readline


N, K = map(int, input().rstrip().split())
A = list(map(int, input().rstrip().split()))

left_p = A[0]
right_p = A[0]
ans = 0

for i in A:
    if left_p <= i <= right_p:
        continue

    if i > right_p:
        right_p = i
    else:
        left_p = i

    if right_p - left_p >= K:
        ans += 1
        left_p = i
        right_p = i

print(ans)

 

728x90

손을 움직여야 하는 횟수를 최소로 하는 문제이다.

 

문제에서 손의 크기는 K로 주어졌고 left_p, right_p 라는 두 가지 변수의 차가 K를 넘지 않도록 최적의 손 위치를 찾으면 된다.

 

list A에서 값을 하나씩 불러와 left_p 와 right_p 범위 안에 있다면 손을 움직일 필요가 없으므로 continue로 빠르게 다음 값을 불러오도록 한다.

 

(불필요한 코드진행을 줄여 실행시간을 단축)

 

이 외의 경우 right_p값 또는 left_p값을 i로 설정하여 손이 움직여야 하는 일정범위를 고정해준다.

 

이때 left_p 와 right_p 범위가 K를 넘어간다면 다음 건반진행을 위해 반드시 손을 움직여야하므로 ans값을 증가시키고, left_p 와 right_p 값을 i로 초기화한다.

 

다음 과정을 반복하면 ans 변수에 손을 옮겨야 하는 최소 횟수를 담을 수 있다.