[백준 27972] - 악보는 거들 뿐 Java

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

27972번: 악보는 거들 뿐

 

음 하나를 연주할 때마다 정수 x를 악보에 쓴다.

다음 음을 연주할 때 더 낮은 음이면 x보다 작은 임의의 숫자를 쓰고,

더 높은 음이면 x보다 큰 임의의 숫자를 악보에 쓴다.

같으면 같은 숫자를 쓴다.

 

예시

만약 악보가 1 3 5 7 9라면 첫 번째 연주한 음에서 계속 증가했다는 의미가 된다.

음이 높으면 더 큰 숫자를 이용하기만 하면 되니깐 1 2 3 4 5로 압축할 수 있는 것이다. (1 2 3 4 5 == 1 3 5 7 9)

최대 5번 증가하기 때문에 5보다 작은 숫자로는 나타낼 수 없다.

 

이 점을 이용하여 가장 연속하여 크게 증가/감소 하는 숫자가 곧 가장 큰 숫자를 나타낼 수 있는 숫자이다.

 

문제 예시 2번 3 1 1 2 1 3은 최대 1번 증가, 최대 1번 감소이다. 따라서 N은 2인데, 이것을 증명해보면

 

첫 번째 3 1 1은 한 번만 감소하기 때문에 2 1 1로 바꿔도 무방하다.

1 1 2 1 3에서 마지막 3은 뒤에 더 증가하는 것이 없고, 한 번 증가하기 때문에 2로 바꿔도 무방하다.

따라서 3 1 1 2 1 3은 2 1 1 2 1 3이 된다.

만약 3 1 1 2 2 3의 경우에는 2 1 1 2 2 3이 된다.

풀이

기존 배열을 저장해두고, 배열을 탐색하면서

최대 연속해서 증가하는 개수를 dp 배열에, 최대 연속해서 감소하는 개수를 dp2 배열에 기록한다.

int[] ary = new int[M];
int[] dp = new int[M];
int[] dp2 = new int[M];

dp[0] = 1;
dp2[0] = 1;
for(int i= 0;i<M;i++) {
  ary[i] = Integer.parseInt(st.nextToken());
}

for(int i= 1;i<M;i++) {
  if(ary[i]>ary[i-1]) {
      dp[i] = dp[i-1]+1;
      dp2[i] = 1;
  }else if(ary[i]<ary[i-1]){
      dp[i] = 1;
      dp2[i] = dp2[i-1]+1;
  }
  else {
      dp[i] = dp[i-1];
      dp2[i] = dp2[i-1];
  }
}

dp 배열과 dp2 배열은 각각 몇 번째로 연속하여 증가/감소 인지에 대한 정보가 기록돼있다.

for(int i= 0;i<M;i++) {
   max = Math.max(max, Math.max(dp[i], dp2[i]));
}

System.out.println(max);

각 배열에서의 최댓값을 찾기만 하면 된다.

정답 코드

package 백준_2024년.스터디_5wnck;

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

public class problem1 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int M = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] ary = new int[M];
        int[] dp = new int[M];
        int[] dp2 = new int[M];

        dp[0] = 1;
        dp2[0] = 1;
        for(int i= 0;i<M;i++) {
            ary[i] = Integer.parseInt(st.nextToken());
        }

        for(int i= 1;i<M;i++) {
            if(ary[i]>ary[i-1]) {
                dp[i] = dp[i-1]+1;
                dp2[i] = 1;
            }else if(ary[i]<ary[i-1]){
                dp[i] = 1;
                dp2[i] = dp2[i-1]+1;
            }
            else {
                dp[i] = dp[i-1];
                dp2[i] = dp2[i-1];
            }
        }
        int max = 0;

        for(int i= 0;i<M;i++) {
           max = Math.max(max, Math.max(dp[i], dp2[i]));
        }

        System.out.println(max);
    }
}