[백준] 20127 Y-수열

1. 문제

www.acmicpc.net/problem/20127

20127번: Y-수열

2. 접근방법

맨 앞 몇 개의 K개의 숫자를 맨뒤로 보냈을 때

증가 or 감소 수열로 만들 수 있는지 묻는 문제

 

문제를 잘못 읽고 맨 앞이 아니라

중간의 숫자도 골라서 뒤로 보낼 수 있는 줄 알고 고생 좀 했다..

 

나 올 수 있는 모양이

증가 수열 ( 3, 4, 5 ) + 증가 수열 ( 1, 2 )

이면 345를 뒤로 보내 증가수열로 만들 수 있다.

즉 수열이 나뉘는 곳 앞의 갯수를 세면 된다.

 

그런데

(3, 4, 5) (1,2) (1,2)

이런 모양이면 불가능하다

수열 변곡이 두번 일어나선 안된다.

 

또

(3,4,5) (1,4)

이 모양도 불가능 하다.

3 4 5 를 뒤로 보내도 1 4 3 4 5 가 되어

증가수열이 될 수 없음.

 

즉 앞 증가수열의 첫번째 수와 뒤 증가수열의 마지막 수가 증가수열 형태면

변경된 증가수열도 증가수열이 되게 된다.

 

수열 변곡이 한번도 없었다면 ans 1이 된다.

 

마이너스 수열도 마찬가지로 생각하고 주의해서 풀이하면 된다.

 

 

3. 자바 코드

package Silver;

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

public class P20127Y수열1 {
	static boolean pline, mline;
	static boolean pcant, mcant;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		int cnt1 = 1;
		int cnt2 = 1;
		int firstnum = Integer.parseInt(st.nextToken());
		int lastnumP = firstnum;
		int lastnumM = firstnum;
		for (int i = 1; i < N; i++) {
			int num = Integer.parseInt(st.nextToken());
			if (!pline) {
				if (lastnumP <= num) {
					lastnumP = num;
					cnt1++;
				}
				else {
					pline = true;
					lastnumP = num;
				}
			} else if(!pcant) {
				if (lastnumP <= num)
					lastnumP = num;
				else
					pcant = true;
			}
			if (!mline) {
				if (lastnumM >= num) {
					lastnumM = num;
					cnt2++;
				}
				else {
					mline = true;
					lastnumM = num;
				}
			} else if(!mcant) {
				if (lastnumM >= num)
					lastnumM = num;
				else
					mcant = true;
			}
		}
		int ans = 100000000;
		if (!pline || !mline) {
			ans = 0;
		} else {
			if (firstnum < lastnumP)
				pcant = true;
			if (firstnum > lastnumM)
				mcant = true;
		}
		if(!pcant)
			ans = Math.min(ans, cnt1);
		if(!mcant)
			ans = Math.min(ans, cnt2);
		if(pcant && mcant)
			ans = -1;
		System.out.println(ans);
	}

}

4. 마치며

처음 문제를 잘못 봐서 삽질하는 시간이 너무 오래걸렸다.

문제를 잘 읽자ㅜ