[BOJ/백준] 28323번 : 불안정한 수열 (Java)

📘 백준 28323번 : 불안정한 수열

---

문제 바로가기

💡 문제 풀이

---

현재의 수를 선택할지 말지가 이후 선택에 영향을 주지 않기 때문에 현재 수가 직전 선택한 수와 다른 홀짝이면 무조건 선택(그리디)

1. 첫 번째 수는 무조건 선택

2. 이후 수를 하나씩 확인하면서 직전에 선택한 수와의 홀짝 여부를 비교

3. 만약 현재 수가 이전 수와 같은 홀짝(홀-홀, 짝-짝)이라면 선택하지 않음

4. 다른 홀짝(홀-짝, 짝-홀)이라면 선택하고 선택한 수의 홀짝 정보를 갱신

5. 이렇게 조건을 만족하는 수들을 최대한 선택한 뒤, 그 총 개수를 출력

✅ 코드 (Java)

---

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

// https://www.acmicpc.net/problem/28323
// 이웃한 자연수의 합이 홀수가 되려면 홀짝 or 짝홀 순서여야 함
// => 주어진 자연수 수열을 확인해가면서 홀홀 or 짝짝이 되는 자연수는 선택하지 않으면서 카운트
public class B28323_불안정한_수열 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine()); // 자연수 개수
		StringTokenizer st = new StringTokenizer(br.readLine());
		int last = Integer.parseInt(st.nextToken()); // 마지막으로 선택한 자연수
		int cnt = 1; // 선택한 자연수 개수
		boolean lastIsEven = (last % 2 == 0); // 마지막으로 선택한 자연수의 홀짝
		for (int i = 1; i < N; i++) {
			int now = Integer.parseInt(st.nextToken()); // 확인할 자연수
			if (lastIsEven == (now % 2 == 0)) { // 홀홀 or 짝짝이면 선택하지 않음
				continue;
			} else { // 현재 자연수를 선택
				cnt++;
				last = now;
				lastIsEven = (last % 2 == 0);
			}
		}
		System.out.println(cnt); // 개수 출력
		br.close();
	}
}

💾 제출 결과

---

보러 가기