글 읽기 - 1201번 제 알고리즘의 오류 질문드립니다!

thyung 4년 전 0

해설을 통해서 M+K-1 <= N <= M*K인 경우에만 조건을 만족할 수 있다는 것을 알았습니다.

----------------------------

22%에서 틀림이 나오네요. 완벽하지 않은 알고리즘인가 봅니다. 제가 어떤 부분을 빼먹은 것인지 궁굼합니다.

일단 K개의 숫자그룹을 만듭니다.

그 다음 N-K개 수에 대해서 (M-1)개 그룹으로 나눕니다(M-2개로 나눈 후, 나머지 개수만큼을 첫 번째 그룹에, 몫개수 만큼을 두 번째 그룹부터에 채웁니다)

그후 각 그룹들을 리버스 합니다.

그후 첫 그룹부터 순서대로 출력합니다

이런 알고리즘으로 생각을 했습니다. 여기서 보충해야 하거나 틀린 부분이 어느 부분인지 알려주시면 감사하겠습니다.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
vector<int> vc[500];
int main() {
	int N, M, K;
	cin >> N >> M >> K;
	if (M + K - 1 <= N && N <= M * K) {
		//vc에 제대로 넣기
		int vccnt = 0;
		for (int i = 1; i <= K; i++) {
			vc[vccnt].push_back(i);
		}
		vccnt++;
		int othersize = N - K;//othersize로 M-1그룹으로 나눠야 함
		int groupsize;//한 그룹당 들어갈 개수
		int last_group_size;//groupsize씩 넣고 남는 개수
		if (M == 1) { //역순 출력
			for (int i = N; i > 0; i--) cout << i << ' ';
		}
		else if (M == 2) { //M이 2이면 M-2개 그룹으로 나누지 못 하므로
			for (int i = K + 1; i <= N; i++) {
				vc[vccnt].push_back(i);
			}
			vccnt++;
			for (int i = 0; i < vccnt; i++) {
				reverse(vc[i].begin(), vc[i].end());
			}
			for (int i = 0; i < vccnt; i++) {
				for (int j = 0; j < vc[i].size(); j++) {
					cout << vc[i][j] << ' ';
				}
			}
		}
		else {
			if (othersize % (M - 2) == 0) {
				groupsize = othersize / (M - 1);
				last_group_size = othersize - groupsize * (M - 1);
			}
			else {
				groupsize = othersize / (M - 2);
				last_group_size = othersize - groupsize * (M - 2);
			}
			for (int i = K + 1; i < K + 1 + last_group_size; i++) {
				vc[vccnt].push_back(i);
			}
			vccnt++;
			for (int i = K + 1 + last_group_size; i <= N; i++) {
				vc[vccnt].push_back(i);
				if (vc[vccnt].size() == groupsize) vccnt++;
			}
			for (int i = 0; i < vccnt; i++) {
				reverse(vc[i].begin(), vc[i].end());
			}
			for (int i = 0; i < vccnt; i++) {
				for (int j = 0; j < vc[i].size(); j++) {
					cout << vc[i][j] << ' ';
				}
			}
		}
	}
	else {
		cout << -1;
	}
	return 0;
}

pichulia 4년 전 1

group_size 나 last_group_size의 크기가 K보다 클 수 있습니다.

20 4 5

thyung 4년 전 0

감사합니다! 그부분을 생각 못 했네요ㅠㅠ다행히 좀 전에 다른 방법으로 풀었어요! 좋은 하루 되세요!!

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

문제

문제

출처

ICPC

1201번 제 알고리즘의 오류 질문드립니다!

thyung 4년 전 0

pichulia 4년 전 1

thyung 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말