https://www.acmicpc.net/problem/11054
먼저 바이토닉 수열 이란 증가하다가 감소하거나 증가만 하거나 감소만하는 수열.
여가서 증감후다시 증가하거나, 감소하다증가하는경우 바이토닉 수열이 아니다.
여기서,
증가하는 수의 갯수를 담을 increase[i][j]배열과 감소하는 갯수를 담을 decrease[i][j]를 정의하는데, 부분 수열들을 다루므로, 앞의 정의중에
감소하다 증가하는경우는 고려할 사항은아니다.
구현할 점화식을 구한 과정이다.
코드를 짜면서 여러 에러가 잦았는데, 원인을 찾기위해 관련된값들을 출력해서 확인했다.
계산중 j = 1 일때 arr[j-1] < arr[j] 의 부등식이 이상하게 작용 해서 확인해보니
increase[1][1]을 무조건 1로 설정해주기위해 안쓰는 arr[0]을 최솟값으로 설정해주었다.
그리고 코딩하다가 한참뒤에 이상한오류가나서 확인해본결과..
i = 1 부터인데 n까지가아닌 (n-1)까지 읽어오고있었다... 여기 고치고 decrease[][]까지 같은 원리로 구현한 코드는 아래와 같다.
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[] arr = new int[n+1];
int[][] increase = new int[n+1][n+1];
int[][] decrease = new int[n+1][n+1];
for(int i = 1 ; i <= n ; i++) arr[i] = scanner.nextInt();
arr[0] = -1; //increase[1][1] = 1로 만들어주기위함
for(int j = 1; j <= n ; j++) {
for(int i = 1 ; i <= j ; i++) { //1 <= i <= j
//1회째 increase[i][j]=0인상태, 다음인자인 점화식이 최댓값이므로 increase[i][j]에 들어감
//n회째 (n-1)회째의 increase[i][j] 값과 점화식중 큰값을 기록
int temp1 = increase[i][j];
int temp2 = increase[i][j-1] + (arr[j-1] > arr[j] ? 1 : 0);
increase[i][j] = Math.max(increase[i][j], increase[i][j-1] + (arr[j-1] < arr[j] ? 1 : 0));
//System.out.println(i + " : " + j + " => " + increase[i][j] + " , increase[i][j]=" + temp1 + " 점화식=" + temp2 + " : arr[j-1]=" + arr[j-1] + " < arr[j]=" + arr[j]);
}
}
for(int j = 1; j <= n ; j++) {
for(int i = 1 ; i <= j ; i++) { //1 <= i <= j
int temp1 = decrease[i][j];
int temp2 = decrease[i][j-1] + (arr[j-1] > arr[j] ? 1 : 0);
decrease[i][j] = Math.max(decrease[i][j], decrease[i][j-1] + (arr[j-1] > arr[j] ? 1 : 0));
//System.out.println(i + " : " + j + " => " + decrease[i][j] + " , decrease[i][j]=" + temp1 + " 점화식=" + temp2 + " : arr[j-1]=" + arr[j-1] + " > arr[j]=" + arr[j]);
}
}
//바이토닉 수열은 increase[i][x] + decrease[x][j](1 <= x <= n)중 최댓값을 구하면된다.
int max_count = 0;
for(int x = 1 ; x <= n ; x++) {
if(max_count < increase[1][x] + decrease[x][n]) max_count = increase[1][x] + decrease[x][n];
//System.out.println(x + " : " + max_count);
}
System.out.println(max_count);
}
}그런데.. 여기까지 코드짜면서 나온 오류들을 나열하자면,
1) n = 1 일때 프로그램이 바로종료 => 앞서 고친 i가 1부터 n까지 작동하지않아서
2) 모든 원소가 같은 원소일때 출력값은 1이어야하나 2가 출력 => increase, decrease가 모두 1이어서 더해서 2가나온것. 이는 지금 코드에는 없지만 decrease[][]만드는 2중포문 바로위에 arr[0] = 0x7fffffff; 을 만들어둬서 나온 오류였음. 제거하니 고쳐짐
3) 마지막부분에 max_count 셀때 2 <= x <= n-1 로잡아서 출력값이 랜덤하게 줄어들엇음..
위 3가지정도가 동시에 작용해서 하나씩 확인하느라.. (대충 8번정도수정..) 이미 멘탈이나간상태에서, 백준채점결과 틀렸다고만 계속 나와서
같은 문제의 다른사람이 짠코드와 출력값을 비교해보니(증가만하는, 감소만하는, 증가감소, 모두같은원소, 원소갯수가3개, 원소갯수2개, 원소갯수1개, 따로 구해놓은 바이토닉수열까지)전부 일치했다..
멘탈이 상당히 갈린상태라 지금으로는 이 코드가 정답인게 100% 확신이되고 오류를 찾을 겨를이없다..
