[BOJ] 32867 - 피아노

1. 문제 정리

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

링크를 확인해보세요.

www.acmicpc.net

• 주어진 건반을 순차적으로 눌려야 합니다.
• 손을 두는 위치를 오른손 엄지를 기준으로 합니다.
  • 따라서 3번 건반에 손을 두었을 경우 손길이가 3이라고 해도 2번 건반 치려면 손을 옮겨야 합니다.
• 초기 손 시작 위치는 원하는 위치에 두고 시작 합니다.

2. 문제 풀이

아이디어

• 순차적으로 x개의 건반을 손을 움직이지 않고 칠 수 있다고 가정 합니다.
• 이를 만족 하기 위해서는 x개의 건반에서 최저 위치와 최고 위치의 차이가 K(손길이) 보다 짧아야 합니다.

결론

• 순차적으로 건반을 리스트에 추가하여 최저 위치와 최고 위치를 차이(diff) 검색합니다.
• CASE 1 : diff >= K
  • 마지막 건반을 제외하고 추가한 건반들은 한 번에 칠 수 있음을 의미하게 됩니다.
• CASE 2 : diff < K
  • 다음 건반을 추가할 수 있음을 의미하게 됩니다.

3. 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    void solve() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        //== 입력 받기 및 초기화
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());   // 눌러야 하는 건반 수
        int K = Integer.parseInt(st.nextToken());   // 손가락 길이

        // 순서대로 눌러야하는 키.
        int[] keys = Arrays.stream(br.readLine().split(" "))
                .mapToInt(Integer::parseInt).toArray();

        int ans = 0;

        // 현재 한 번에 치려고 하는 키들에서 최소와 최대
        int minKey = keys[0], maxKey = keys[0];

        for (int key: keys) {
            minKey = Math.min(key, minKey);
            maxKey = Math.max(key, maxKey);
            
            // 차이가 K 이상일 때 손을 움직여야 함.
            // 또한 치려고하는 키들이 현재키로 초기화.
            if (maxKey - minKey >= K) {
                ans += 1;
                minKey = maxKey = key;
            }
        }
        System.out.println(ans);
    }

    public static void main(String[] args) throws Exception {
        new Main().solve();
    }
}