글 읽기 - 예제도 다 맞고, 제가 만든 예제도 맞는데 뭐가 문제인지 모르겠어요.

pinkish15 7년 전 0

저는 문제를 패턴 형식으로 생각했고, 패턴이 같은 경우와 패턴이 다른 경우로 나누어서 문제를 풀었어요.

1. 먼저 현재상태 패턴과 목표상태 패턴이 모두 같은 경우 -> 다 돌려주면 됌 (ex. 444와 555는 일치)

2. 패턴이 다를 경우

그중 2개의 패턴이 일치할 경우

1) 2번째 패턴과 3번째 패턴이 일치하는 경우(ex. 123과 467의 경우) -> 넘어간다. 왜냐면 다음 수를 합쳤을 때, 234랑 678이면 한번에 돌릴 수 있고, 아니어도 2-2)으로 돌려주면 되기에.

2) 1번째 패턴과 2번째 패턴이 일치하는 경우(ex. 237과 678의 경우) -> i번째와 i+1번째의 현재상태를 목표상태로 바꿔준다.

3) 1번째 패턴과 3번째 패턴이 일치하는 경우(ex. 135와 175의 경우) -> i번째와 i+2번째의 현재상태를 목표상태로 바꿔준다.

를 N-2번 돌리고

현재상태와 목표상태가 일치하지 않는 디스크들을 한번씩 돌려주었는데요,

예제도 다 맞고 직접 만든 예제도 다 맞는데 어디에서 반례가 생기는지 궁금해서 질문 올려요!

#include <stdio.h>

int main(void) {

	int N;
	char x;
	int obj[100];
	int cur[100];
	int patC[3] = { 0 };
	int patO[3] = { 0 };
	int count = 0;

	scanf("%d", &N);
	
	for (int i = 0; i < N; i++) { //current
		scanf(" %c", &x);
		cur[i] = atoi(&x);
	}

	for (int i = 0; i < N; i++) { //object
		scanf(" %c", &x);
		obj[i] = atoi(&x);
	}

	for (int i = 0; i < N-2; i++) {
		patC[0] = cur[i + 1] - cur[i];
		patC[1] = cur[i + 2] - cur[i];
		patC[2] = cur[i + 2] - cur[i + 1];
		patO[0] = obj[i + 1] - obj[i];
		patO[1] = obj[i + 2] - obj[i];
		patO[2] = obj[i + 2] - obj[i + 1];
		//[0]은 두번째-첫번째, [1]은 세번째 - 첫번째, [2]는 세번째 - 두번째

		if (patC[0] == patO[0] && patC[1] == patO[1] && patC[2] == patO[2]) {
			//패턴이 같은 경우
			if (cur[i] == obj[i] && cur[i + 1] == obj[i + 1] && cur[i+2] == obj[i+2]) continue;
			cur[i] = obj[i];
			cur[i + 1] = obj[i + 1];
			cur[i + 2] = obj[i + 2];
			count++;
			i += 2;
		}
		else {
			if (patC[2] == patO[2]) { //두번째 - 3번째 같은경우
				continue;
			}
			else if (patC[0] == patO[0]) { //첫번째 - 2번째 같은경우
				if (cur[i] == obj[i] && cur[i + 1] == obj[i + 1]) continue;
				cur[i] = obj[i];
				cur[i + 1] = obj[i + 1];
				count++;
			}
			else if (patC[1] == patO[1]) { //첫번째 - 3번쨰 같은경우
				if (cur[i] == obj[i] && cur[i + 2] == obj[i + 2]) continue;
				cur[i] = obj[i];
				cur[i + 2] = obj[i + 2];
				count++;
			}
		}
	}

	for (int i = 0; i < N; i++) {
		if (cur[i] != obj[i]) {
			cur[i] = obj[i];
			count++;
		}
	}

	printf("%d\n", count);
	return 0;
}

simm4256 7년 전 2

5

11111

23432

3이 정답입니다. 이 코드는 4를 출력하네요

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