[BOJ 28361] 크리스마스

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

28361번: 크리스마스

 

- 문제 요약

 

20XX년의 크리스마스가 다가옴에 따라 산타클로스는 선린 마을에 선물을 나눠주려고 한다.

선린 마을에는 1부터 N까지의 번호가 매겨진 집이 있다.

집은 번호가 증가하는 순으로 원형을 이루고 있다.

즉, 1 ≤ i < N인 모든 i에 대해 i번 집과 i+1번 집은 이웃해 있고, N번 집과 1번 집 또한 이웃해 있다.

이웃한 집 사이의 거리는 1이다.

산타클로스는 1번 집부터 시작해서 모든 집에 방문해 선물을 나눠준 뒤, 다시 1번 집으로 돌아올 것이다.

산타클로스는 마을 사람들이 잠에서 깨지 않도록 하기 위해 아래 규칙을 따라 이동하려 한다.

• 시계 방향 또는 반시계 방향으로 현재 집에서 거리가 2 이하인 집에만 갈 수 있다.
• 세 번 연속 같은 방향으로 갈 수 없다.
• 같은 집을 두 번 연속으로 방문할 수 없다.

같은 집을 두 번 연속으로 방문할 수 없지만, 다른 집을 거친 다음에 다시 방문하는 것은 가능하다.

 1번 집에서 출발하여 가능한 한 적게 이동하며 모든 집을 방문하고 1번 집으로 돌아올 때 이동 횟수와 방문 순서를 출력하여라.

 

 

- 알고리즘 정리

 

왼쪽 또는 오른쪽으로 2칸 이동하고 반대 방향으로 1칸 이동하면 한 방향으로 쭉 갈 수 있습니다.

그러므로 3개의 인접한 집에 방문할 수 있고, N이 3K, 3K+1, 3K+2인 경우를 나눠서 주어진 조건을 처리해 주면 됩니다.

 

 

- 코드 작성

 

#include <bits/stdc++.h>
using namespace std;

#define MAX 1000001
int n, arr[MAX];

int main(){
    ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
    cin>>n;
    arr[1]=1;
    if(n%3==0){
    	for(int i=1; i<=n; i+=3){
    		arr[i]=-1;
    		arr[i+1]=2;
			arr[i+2]=2;
		}
	}
    if(n%3==1){
    	for(int i=1;i<=n;i+=3){
    		arr[i]=2;
			arr[i+1]=-1;
			arr[i+2]=2;
		}
	}
    if(n%3==2){
    	for(int i=2; i<=n; i+=3){
    		arr[i]=2;
			arr[i+1]=-1;
			arr[i+2]=2;
		}
	}
    partial_sum(arr,arr+n+1,arr);
    cout<<n<<'\n';
    for(int i=0;i<n;i++){
    	cout<<(arr[i]+n)%n+1<<" ";
	}
    cout<<1;
}