BOJ2478 자물쇠

www.acmicpc.net/problem/2478

2478번: 자물쇠

 

 

 

입력에 맞는 답 (k1, p, q, k2)가 여러 개 존재한다. 아래처럼 둘 중 뭐가 돼도 상관없다는 걸 먼저 파악함. 그 다음엔 가장 구하기 편한 걸 구하기로 했다.

(3, 5, 7, 3): 12345678 → 45678123 → 45672183 → 72183456

(5, 3, 5, 1): 12345678 → 67812345 → 67218345 → 72183456

 

아래 여섯 가지 예시로 생각해보았다. 밑줄이 뒤집어진 부분

ex	input	Step 1	Step 2	Step 3	(k1, p, q, k2)
①	7 2 1 8 3 4 5 6	p=2 q=4 x=3	k2=8	k1=6	(6, 2, 4, 8)
②	4 7 6 5 8 1 2 3	p=2 q=4 x=6	k2=8	k1=3	(3, 2, 4, 8)
③	7 3 4 5 6 2 1 8	p=6 q=1 x=7	k2=3 p=1 q=4 x=2	k1=6	(6, 1, 4, 3)
④	6 5 4 8 1 2 3 7	p=8 q=3 x=5	k2=1 p=1 q=4 x=2	k1=3	(3, 1, 4, 1)
⑤	8 7 6 5 4 3 2 1	p=1 q=8 x=1	k2=8	k1=8	(8, 1, 8, 8)
⑥	3 2 1 4 5 6 7 8	p=1 q=3 x=1	k2=8	k1=8	(8, 1, 3, 8)

 

Step 1. 처음 입력받은 배열 상 x, p, q를 찾는다. (x = 1의 위치)

for문 돌려서 a[i+1]-a[i] != 1, -1, 1-N, N-1 => p=i+1, q=i, (p, q 순차적으로) 구한다

 

예외처리한다.

1)  8 7 6 5 4 3 2 1 ⑤

for문이 끝나도 p=q=0이 됨. 수열 전체를 뒤집은 경우이기 때문에 p=1, q=N으로 설정

 

2)  3 2 1 4 5 6 7 8 ⑥

for문이 끝나면 p=4, q=0이 되어있음. p=1, q=p-1로 바꿈. 여기선 p=1, q=3이 되겠다.

 

3)  7 3 4 5 6 2 1 8 ③. ④도 마찬가지다.

for문에 따르면 '7 3'에 의해 p=2, '6 2'에 의해 q=5라고 구해짐. 순방향인 구간을 고른 것이다.

p=q+1, q=p-1로 바꿔준다. (p=i+1, q=i로 구하는 거니까) 따라서 표와 같이 p=6, q=1을 얻을 수 있음.

 

 

Step 2. k2 구한다.

if)  p<q ①②⑤⑥

k2=N으로 둔다. k1만큼 왼쪽으로 이동, p, q 바꾸고, 한 바퀴 돌린 결과라고 하면 되니까

 

else)  ③④

역방향인 구간이 앞부분과 뒷부분에 걸친 경우이다.

k2=N-p+1로 두고 p, q, x에 각각 k2만큼 더해서 결과적으로 p=1이 되도록 옮긴다.

이때 x>N이면 N을 한 번 더 빼주는 거 잊지 말고

③의 경우 k2=8-6+1=3에 의해 2 1 8 7 3 4 5 6 → 7 3 4 5 6 2 1 8 가 됐다.

 

 

Step 3. k1 구한다.

처음 위치가 1이었던 수는 왼쪽으로 N-x+1만큼 움직여야 x에 위치한다. (1-move+N=x ⇒ move=N-x+1)

 

if)  p≤x≤q ①③⑤⑥

뒤집으면 x의 위치가 p+(q-x)로 바뀐다. k1=N-(p+(q-x))+1=N-p-q+x+1

 

else)  ②④:  k1=N-x+1

 

 

코드

#include <cstdio>
using namespace std;

int main() {
	int a[501], N, k1, k2, p, q, x, tmp;
	scanf("%d", &N);
	for (int i = 1; i <= N; ++i) scanf("%d", &a[i]);

	k1 = k2 = p = q = x = 0;//= y = 0;
	for (int i = 1; i < N; ++i) {
		if (a[i] == 1) x = i;

		tmp = a[i + 1] - a[i];
		if (tmp == 1 || tmp == -1 || tmp == N - 1 || tmp == 1 - N) continue;

		if (!p) p = i + 1;
		else if (!q) q = i;
	}
	if (!p && !q) p = 1, q = N;		//(87654321)
	else if (!q) q = p - 1, p = 1;		//4321)(8765
	if (!x) x = N;

	if (a[p] == a[p + 1] - 1 || (a[p] == N && a[p + 1] == 1)) {
		tmp = p, p = q + 1, q = tmp - 1;
		k2 = N - p + 1, p = 1, q += k2, x += k2;
		if (x > N) x -= N;
	}
	else k2 = N;
	//if:   654)8123(7 7)3456(218
	//else: 7(218)3456 4(765)8123

	if (p <= x && x <= q) k1 = N - p - q + x + 1;
	else k1 = N - x + 1;
	//if:   7(218)3456 7)3456(218
	//else: 654)8123(7 4(765)8123

	printf("%d\n%d %d\n%d\n", k1, p, q, k2);
	return 0;
}

 

 

여러 번 틀린 문제. 역시나 처음에 ①~④만 생각하고 대충 냈다가 틀렸습니다 받음,, 한 번 더 고쳐서야 맞았다.

유연한 사고가 되지 않아서 저번에 풀 때나 이번에 풀 때나 가능한 경우를 다 생각해보는 방식으로 풀었는데

 

좀 조잡한 것 같기도 하고