글 읽기 - 반례 질문

jsjsjs0775 3년 전 0

아래와 같은 코드로 통과가 됐거든요.

아래 코드 풀이 논리는 증가수열 갯수를 찾는건데,

이 증가수열을 최대한 더 줄이는 방식으로 짜지 않으면 틀리도록 하는 반례가 없는 것 같아서요.

저가 반례를 구체적으로 만들지는 못하겠지만..

그런 반례는 불가능한가요?

#include <iostream>
#include <queue>
#include <algorithm>
#include <cstring>
#include <vector>
#include <stack>
using namespace std;
int N, K;
int arr[101];
int vis[101];

int main(void) {

	//freopen("input.txt", "r", stdin);
	cin.tie(0); ios_base::sync_with_stdio(0);
	cin >> N>> K;
	for (int i = 1; i <= N; i++) {
		int x; cin >> x;
		arr[i] = x;
	}

	int cnt = 0;

	for (int i = 1; i <= N; i++) {

		if (vis[i] == 0) {

			cnt++;

			int big = arr[i];

			for (int j = i + 1; j <= N; j++) {

				if (big < arr[j] && vis[j] == 0) {

					vis[j] = 1;
					big = arr[j];
				}
			}
		}
	}
	if (cnt > K) cout << "NO";
	else cout << "YES";
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

반례 질문

jsjsjs0775 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말