문제 바로가기 >
설명 & 입출력
해설
이 문제를 풀기 위해선 처음 1~N까지의 카드를 어떻게 배열할지를 알아야 한다.
이떄 어떻게 배열을 해도 무조건 모든 카드를 뒤집을 수 있는 배열법이 존재한다.
이 배열법은 간단하게도 짝수는 오른쪽 끝으로 홀수는 왼쪽끝으로 차례대로 이동을 시키면 끝난다.
ex)
1~5까지의 카드가 있을 경우
배열: 5, 3, 1, 2, 4
ex)
1~3까지의 카드가 있을 경우
배열: 3, 1, 2
위와 같이 배열한 이후 카드를 뒤집는 순서를 정한다.
ex)
맨 처음 숫자 1이 적힌 카드를 뒤집고 n 까지 카드에 적힌 숫자의 순서대로 뒤집는다.
배열: 3, 1, 2
순서: 2, 3, 1
1 -> 2 -> 3
위의 과정을 거치면 모든 카드를 뒤집을 수 있다.
아래는 위의 과정을 실행하는 코드이다.
코드
// fs 패키지 불러오기
const fs = require("fs");
// input 값 받기
const input_single: number = Number(fs.readFileSync('/dev/stdin').toString());
// 초기 배열
const arr: number[] = [];
// 결과 배열
let reulst: number[] = [];
// 초기 배열 초기화
for(let i=1; i<=input_single; i++) {
// 짝수일 경우 오른쪽 끝으로 보내기
// 홀수일 경우 왼쪽 끝으로 보내기
if(i%2 === 0) arr.push(i);
else arr.splice(0, 0, i);
}
// 뒤집을 카드의 인덱스
// 초기값 = 1이 적힌 카드의 인덱스
let curr_index: number = arr.indexOf(1);
// 결과 배열 초기화
for(let i=1; i<=input_single; i++) {
// 뒤집은 카드의 위치를 결과 배열에 집어넣는다.
reulst.push(curr_index+1);
// 왼쪽으로 갈지 오르쪽으로 갈지 정한다
// 후에 뒤집어야 할 카드가 짝수 일 경우 curr_index에 현재 카드의 수 만큼 빼기 아닐경우 더하기
curr_index += i%2 === 0 ? -arr[curr_index] : arr[curr_index];
}
// 결과 출력
console.log("YES");
console.log(arr.join(' '));
console.log(reulst.join(' '));마무리
초기에 카드들을 어떻게 배열하는지에 대한 힌트를 못 봤으면 절대로 못 풀었을 것 같은 문제였다...
다음부턴 문제를 보고 어떤 규칙이 있는지 파악하는데 시간을 더 들여야겠다는 생각이 들었다.
