글 읽기 - 1201번 풀이에서 어디가 틀렸는지 알고 싶습니다.

thyung 4년 전 0

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

그 후 숫자배열을 M개로 나누는데, 적어도 하나의 구간에 K개의 수가 포함되게 하였습니다.(나머지는 K개 이하)

그후 각 구간을 리버스 해 줌으로써 문제를 풀었는데 틀렸다고 나오네요,,어느 부분에서 틀린 것일까요?

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
	int N, M, K;
	cin >> N >> M >> K;
	if (M + K - 1 > N || N > M * K) {//이 조건일 때는 문제를 만족시키는 답이 없다
		cout << '-1\n';
		return 0;
	}
	int arr[500];
	for (int i = 0; i < N; i++) {
		arr[i] = i + 1;
	}
	vector<int> idxs;
	idxs.push_back(0);
	idxs.push_back(K);
	int idx_mod = (N - K) / (M - 1);
	for (int i = 0; i < M - 1; i++) {//인덱스 넣기
		if (i == M - 2) idxs.push_back(N);//마지막에는 /로 인해 버려진 값 때문에 인덱스를 따로 설정
		else idxs.push_back(idxs.back() + idx_mod);
	}
	for (int i = 0; i < idxs.size()-1; i++) {
		reverse(arr + idxs[i], arr + idxs[i + 1]);
	}
	for (int i = 0; i < N; i++) {
		cout << arr[i] << ' ';
	}
	cout << '\n';
	return 0;
}

pjok1122 4년 전 3

20번째 줄에서 M=1이라면 ZeroDivisor 예외가 발생합니다.

2. idx_mod를 버림으로 계산하시면, 원치않는 결과를 얻을 수 있습니다.

예를 들어, 7 4 2 라고 하면 1 2 3 4 5 6 7을 1 2 / 3 4 5 6 7 으로 나누게 됩니다.

여기서 남은 숫자가 5개이고, 필요한 그룹 수는 3이므로 idx_mod = 1이라고 계산하시는데, 이렇게 나눌 경우,

1 2 / 3/ 4/ 5 6 7 으로 묶이기 때문에 오답이 나올 수 있습니다.

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

문제

문제

출처

ICPC

1201번 풀이에서 어디가 틀렸는지 알고 싶습니다.

thyung 4년 전 0

pjok1122 4년 전 3

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말