BOJ 1449 수리공항승 [C언어]

// 백준 문제 : 수리공 항승
// 문제 레벨 : 실버 3


#include <stdio.h>
#include <stdlib.h>



int main(){
	
	int leakCount;
	int tapeLenth;
	int * loc = NULL;

	int i, j;
	int left, point;
	int count = 0;
	
	scanf("%d %d", &leakCount, &tapeLenth);
	
	loc = (int*)malloc(sizeof(int)*leakCount);
	for(i = 0; i < leakCount; i++) {
   	scanf("%d", &loc[i]);
   }
	
	// tester
/*	printf("| leakCount: %d, tapeLenth: %d\n", leakCount, tapeLenth);
	
	printf("*** Array ***\n|");
	for(i = 0; i < leakCount; i++) {
		printf("%d ", loc[i]);
	}
	printf("\n");
*/

	// 첫 번째 테이프 붙이기
	count++;
	left = tapeLenth;
	// 두 번째 구멍까지 커버할 수 있을까?
	for(i = 1; i < leakCount; i++) {
		if(loc[i] - loc[i-1] <= left) {
			left -= loc[1] - loc[0];
		} else {
			count++;
			left = tapeLenth;
		}
	}
	
	// result
/*	printf("The answer is : %d\n", count);
*/

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

위는 내가 처음에 작성한 코드. 딱 봐도 가독성도 낮고 오류가 많아보인다.

 

아니나 다를까, '틀렸습니다.'

 

반례를 찾았다. 그냥 이것저것 예시 넣어보다가

반례1)

7 20

1 6 7 8 9 12 15

 

정답은 1인데, 내 코드상으로는 2가 나왔다.

 

디버깅 코드를 넣어서 반복문이 돌아가는 동안 변수에 이상이 있는지 확인했다.

디버그 결과)

F left : 20
| loc[1] - loc[0] = 5
| left : 15
| loc[2] - loc[1] = 1
| left : 10
| loc[3] - loc[2] = 1
| left : 5
| loc[4] - loc[3] = 1
| left : 0
| loc[6] - loc[5] = 3
| left : 15
2

 

 

//debug
			printf("| loc[%d] - loc[%d] = %d\n", i, i-1, loc[i]-loc[i-1]);
			printf("| left : %d\n", left);

그랬더니 틀린 부분을 찾았다.

남은 테이프 길이를 연산하는 과정에서 i와 i-1 대신에 1과 0을 잘못 넣어서
연산이 제대로 이루어지지 않았던 것이다.

 

고친 코드다.

	for(i = 1; i < leakCount; i++) {
		if(loc[i] - loc[i-1] <= left) {
			left -= loc[i] - loc[i-1];

 

시발근데 또틀렸다.

왜지? 대체...

반례를 찾아보자.

손쉽게 백준 [질문] 탭에서 찾을 수 있었다.

https://www.acmicpc.net/board/view/70795

글 읽기 - Python 1449번 반례 부탁드립니다...

 

반레 2)

4 3

1 2 3 4

 

답은 2인데 나는 1이 나와버렸다.

 

다시 디버그 해보았다.

찾았다.

파이프를 막는 테이프 여유길이 0.5를 고려하지 못해서 나타난 결과였다.

고쳐주었다.

 

if(loc[i] - loc[i-1] +1 <= left)

 

하지만

지랄하지마 진짜

 

후..... 다시 심호흡을 하고 반례를 찾아보자.

 

그렇게 찾은

반례 3)

2 1

3 1

내답 : 1, 정답 : 2

이게말이되냐? 아니 당연히 물 새는 곳은 오름차순으로 주는 줄 알았지...

 

내 코드는 배열이 오름차순으로 정렬되었다고 가정한다..

 

뭐 이건 정렬만 하면 되니 큰 문제는 아니다.

 

그래서 호다닥 선택 정렬 함수를 만들어 넣었다.

 

void selectSort(int * arr, const int length) {
	int i, j, k;
	int temp, minn, minidx;
	for(i = 0; i < length-1; i++) {
		minn = arr[i];
		minidx = i;
		for(j = 1; j < length-i; j++) {
			if(arr[i+j] < minn) {
				minn = arr[i+j];
				minidx = i+j;
			}	
		}		
		temp = arr[i];
		arr[i] = arr[minidx];
		arr[minidx] = temp;
	}
}

 

다시 제출.

 

ㅋㅋㅋㅋㅋ 아 이거지 너무좋아~~ **^^7

 

아래는 전체 소스코드입니다.

// 백준 문제 : 수리공 항승
// 문제 레벨 : 실버 3


#include <stdio.h>
#include <stdlib.h>


void selectSort(int * arr, const int length);

int main(){
	
	// 변수 선언
	int leakCount;			// 물이 새는 곳의 개수 N
	int tapeLenth;			// 테이프의 길이 L
	int * loc = NULL;		// 물이 새는 곳의 위치 배열

	int i;
	int left;				// 테이프의 남은 길이를 저장할 변수
	int count = 0;			// 필요한 테이프의 개수 (정답)
	
	
	// 입력 PART
	scanf("%d %d", &leakCount, &tapeLenth);
	
	loc = (int*)malloc(sizeof(int)*leakCount);
	for(i = 0; i < leakCount; i++) {
   	scanf("%d", &loc[i]);
   }
   
   
   // 배열 선택정렬
   selectSort(loc, leakCount);
	
	


	// 첫 번째 테이프 붙이기
	count++;
	left = tapeLenth;
	

	// 본 문제의 핵심 연산 PART
	for(i = 1; i < leakCount; i++) {
		if(loc[i] - loc[i-1] +1 <= left) {
			left -= loc[i] - loc[i-1];			} else {
			count++;
			left = tapeLenth;
		}
	}
	
	// 출력 PART
	printf("%d", count);
	
	// 동적할당 반환
	free(loc);
	
	
	return 0;
}


void selectSort(int * arr, const int length) {
	int i, j, k;
	int temp, minn, minidx;
	for(i = 0; i < length-1; i++) {
		minn = arr[i];
		minidx = i;
		for(j = 1; j < length-i; j++) {
			if(arr[i+j] < minn) {
				minn = arr[i+j];
				minidx = i+j;
			}	
		}		
		temp = arr[i];
		arr[i] = arr[minidx];
		arr[minidx] = temp;
	}
}