[백준 C++] 8981 입력숫자

문제

아래 mystery.c는 입력파일 X를 읽어서 그 안에 기록된 N개의 정수를 배열 NUM에 저장한 뒤에 이 N개의 수를 어떤 순서에 따라서 화면에 출력하는 프로그램이다. mystery.c가 X를 입력으로 받아 화면에 출력한 결과를 Y라고 하자.
여러분은 mystery.c에서 생성된 Y를 파일로 받아서 그것의 입력에 해당하는 X를 찾아내는 프로그램을 작성해야 한다.

입력

첫 줄에는 정수 N (1 ≤ N ≤ 30)이 주어진다. 그리고 두 번째 줄에는 100이하 양의 정수 N개가 빈칸을 사이에 두고 모두 나열되어 있다. 단 그 정수 중에는 같은 수가 있을 수도 있다.

출력

첫 줄에는 정수 N이 제시되어 있고, 그 다음 줄에는 N개의 양의 정수가 빈칸을 사이에 두고 기록되어 있어야 한다. 만일 입력을 생성하는 mystery.c의 입력파일 X가 없는 경우에는 음수인 -1 을 첫 줄에 출력하면 된다.

https://www.acmicpc.net/problem/8981

풀이

즉, 주어지는 Y를 가지고 X를 구하라는 문제이다.
초깃값 x[0] = y[0]을 주고,
y[i] 부터 y[n-1] 까지 반복하여,
x[i]만큼 건너뛴 위치에 y[i]를 넣는데, 이미 값이있는경우
x[i++] 하라는 문제이다.
처음에는 이렇게 X를 구한뒤,
다시 X -> Y로의 검산함수를 작성하였으나,
문제의 함수내부에서 인덱스는 항상 같은방향으로 증가하는방향으로만 흐르는점으로, 불가능한경우가 생길수가없어서 지웠다.
즉 변수가 없는 문제이므로 출력값 Y가 있는한 무조건 X는 있을 수 밖에 없다는점.

#define _CRT_SECURE_NO_WARNINGS 
#include <bits/stdc++.h>
int n, *x, *y;
void init();
void func();

void func() {
	printf("%d\n", n);
	//초깃값
	x[0] = y[0];
	int cur = 0;
	for (int i = 1; i < n; i++) {
		int value = x[cur];
		cur = (cur + value) % n; //밸류값만큼 커서이동
		while (x[cur] != -1) cur = (cur + 1) % n; //이미 다른값이있으면 +1씩 이동
		x[cur] = y[i]; //다음 출력값을 해당위치에 저장
	}

	for (int i = 0; i < n; i++) printf("%d ", x[i]);

}

void init() {
	scanf("%d", &n);
	x = new int[n];
	y = new int[n];
	for (int i = 0; i < n; i++) {
		scanf("%d", &y[i]);
		x[i] = -1;
	}
}

int main(void) {
	init();
	func();
	
	return 0;
}

좋은 웹페이지 즐겨찾기