S
SCCC
Soongsil Computing Contest Club

14467. 소가 길을 건너간 이유 1

for
array

문제

14467. 소가 길을 건너간 이유 1

문제 요약

N <= 100

건넌 결과는 0 or 1.

소의 번호와 관찰기록이 주어지고 의미없는 위치도 주어질 수 있다.

이 관찰 기록을 가지고 소가 최소 몇 번 길을 건넜는지 알아보자. 즉 같은 번호의 소가 위치를 바꾼 것이 몇 번인지 세면 된다.

풀이

알고리즘이 없는 단순 구현문제다. 소의 번호를 구분하고 그 소가 움직였는지 안움직였는지 체크하는 것이 전부다.

문제만 간단하게 본다면 움직였을때 무조건 횟수를 올리면 된다고 생각하겠지만 (모두가 그렇게 보진 않겠지만 나는 그래서 두번 틀렸다 멍청이) 약간의 훼이크가 있기 때문에 주의하자.

멍청이민주

예제에서도 대놓고 보여주는 훼이크를 문제만 슥 읽고 바로 구현해버렸다간 나처럼 된다.

예제를 들어 쉽게 얘기하자면 먼저 3 1 이 주어지고 3번 소의 최초 위치가 선언된다. 그리고 3 0을 입력받으면서 1에서 0으로 이동을 한다는 것을 알 수 있다. 그 다음 3번소의 움직임이 가장 중요한 포인트다.

0을 입력받은 상태에서 또 0을 입력받은 것이다. 즉 이 INPUT은 소가 이동했을때의 경로를 보여주는 것이 아니라 이동에 상관없이 소의 상태를 보여주는 INPUT 인거다.

그러니 i번소의 가장 이전 위치와 같은지 안같은지 따진 후 count를 해야하는 것이다.

나는 구조체를 이용해 두가지 변수를 선언한 후 배열로 선언해 주었다. 두가지 변수로 먼저 move = 이 소가 최초로 등장한 것인가 Y/N 의 유무를 위해 선언하였고 두번째로 which = 이 소가 있었던 위치를 선언해 주었다.

아래 내 코드를 보면 move가 0이면 한번도 등장한적이 없던 소기 때문에 최초 등장 갱신(move=1)만 해준 후 위치정보를 저장하고 Count는 하지 않도록 짰다.

move가 1이면 이미 소가 등장했었다는 뜻이고 그다음 앞서말한 중요한 부분이 나온다. 이전 위치와 같은 위치가 아닐 때 Count하고 N번의 이동정보가 끝난 후 printf로 cnt를 출력해준다.

이번 코드에서 얻게 된 교훈으로는 쉬워보인다고 나대면서 풀지말자.. 를 얻게 되었다.

처음엔 과외학생도 풀게 할만한 난이도 라는 생각을 했다가 두번틀린 이후로 나자신에 대해 반성하게 되었다.

코드

#include<stdio.h>

struct Cow
{
	int which, move;
};

Cow arr[15] = { 0 };
int N,cnt=0;

int main(void) {
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);

	scanf("%d ", &N);

	for (int i = 0; i < N; i++) {
		int a,b;
		scanf("%d %d ", &a,&b);
		if (arr[a].move == 0) {
			arr[a].move = 1;
			arr[a].which = b;
		}
		else {
			if (arr[a].which != b) {
				cnt++;
				arr[a].which = b;
			}
		}

	}
	printf("%d", cnt);
}
⤧  Next post 14464. 소가 길을 건너간 이유 4 ⤧  Previous post USACO January 2008 Silver 3: Telephone Lines