[C] 백준 | 1654번 코드 - 랜선자르기

>문제

> 핵심

이분탐색

long long 자료형

>풀이과정

(내가 처음 생각한 계획

K개의 랜선 중 제일 짧은 랜선을 찾는다 -> k_min

1부터 k_min까지 1씩 ++하면서 N개 이상의 랜선을 만들어내면 len과 대조해 큰 값을 넣는 계획이었는데..

이중반복문을 돌리다 보니 시간초과가 뜬다..)

 

그래서 어떻게 할까.. 고민하다가 이진탐색 방법이 딱 생각났다!!

K개의 랜선 중 제일 긴 랜선을 찾는다 -> k_max

이진탐색을 위해 left, mid, right 선언

left = 0, right = k_max부터 시작해 mid=(left+right)/2

 

K개의 랜선을 mid 길이로 잘랐을때 N개의 랜선이 만들어지면?

-> mid보다 더 길게 잘라도 N개의 랜선이 만들어질 수 있으니 left = mid+1 후 탐색 진행

 

K개의 랜선을 mid 길이로 잘랐을때 N개의 랜선이 만들어지지 못했다면..?

-> mid보다 더 짧게 잘라야 N개의 랜선이 만들어질 수 있으니 right = mid-1 후 탐색 진행

 

이렇게 탐색을 돌면서 랜선의 최대 길이를 찾아내는 과정이다.

 

이렇게 코드를 짰는데.. 암만봐도 문제가 없어보이는데 틀렸다고 뜬다. 왜그럴까??

 

이유는..

문제 중 다음과 같은 조건 때문이다.

이진탐색을 할 때, mid값을 구하기 위해 mid = (left + right) / 2 를 구하는 과정을 거치는데,

랜선의 최대 길이가 (2^31)-1이기 때문에 left + right를 하는 과정에서 int의 범위를 초과할 수 있기 때문이다!!!

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

세상에나 ㄷㄷ...

전혀 생각지도 못한 문제였다. 괜히 이 문제의 정답률이 20%대에 머무르는게 아니었다..

 

이렇게 된 김에 정수 자료형에 대해 다시한번 복습하게 됐다.

 

 

int	4Byte	-2,147,483,648~ 2,147,483,647
unsigned int	4Byte	0~4,294,967,295
long	4Byte	-2,147,483,648~ 2,147,483,647
long long	8Byte	-9,223,372,036,854,775,808~ 9,223,372,036,854,775,807

unsigned는 문자의 부호를 결정하는 맨앞자리를 양의 범위 표현하는데 써서 일반 int보다 표현범위가 양으로 두배 크다.

 

그리고 4Byte짜리 int와 long은 표현범위가 동일한 것을 알 수 있는데, 그럼 굳이 존재하는 이유가 뭘까??

이는.. 좀 복잡하다.. 구글에 검색을 해봤는데 뭔가 확 와닫는 느낌이 아니다.

하지만 32bit/64bit 프로그램이 있듯이 시스템이 받아들이는 자료형이 다르기 때문...?? 이라는 것 같다.

이건 좀 더 공부가 필요할 것 같다. 추후 작성

 

그리고 long long은 8Byte로 int형 보다 훨씬 방대한 범위의 자료를 담을 수 있다.

그래서 이 문제에서는 long long 형을 이용하여 이진탐색을 해야 정답처리가 되었던 것이다. ㅜㅜ

>깨달은점

int와 long의 차이점에 대해 더 공부하기

정수 자료형의 표현범위에 대해 알기

이진탐색 활용 알기

>코드

이분탐색

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

int main()
{
	int N, K, i, j;
	long long k_max = 0, max_len = 0, cnt;
	long long * list = NULL;
	scanf("%d %d", &K, &N);

	list = (long long *)calloc(K, sizeof(long long));

	for (i = 0; i < K; i++)
	{
		scanf(" %lld", &list[i]);
		if (list[i] > k_max) /*K개의 랜선 중 제일 큰애 찾기*/
			k_max = list[i];
	}

	long long left, mid, right;
	left = 1; right = k_max;

	while (left <= right)
	{
		mid = (left + right) / 2;

		for (j = 0, cnt = 0; j < K; j++)
		{
			cnt += list[j] / mid; /* 각 랜선마다 몇칸씩 나오는지 체크*/
		}

		if (N <= cnt && max_len < mid)
			max_len = mid;

		if (cnt < N)
			right = mid - 1;
		else
			left = mid + 1;

	}

	printf("%lld\n", max_len);

	return 0;
}

(시간초과나는 반복문 코드..)

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

int cutting(int len, int size)
{
	if (len < size)
		return 0;
	
	int cnt = 1;
	return cnt + cutting(len - size, size);
}

int main()
{
	int N, K, i, j, len = 0, k_min = 10000, cnt;
	int* list = NULL;
	scanf("%d %d", &K, &N);
	
	list = (int*)calloc(K, sizeof(int));

	for (i = 0; i < K; i++)
	{
		scanf(" %d", &list[i]);
		if (list[i] < k_min)
			k_min = list[i];
	}

	for (i = 1; i <= k_min; i++)
	{
		for (j = 0, cnt = 0; j < K; j++)
		{
			cnt += cutting(list[j], i);
		}
		if (N <= cnt && len < i)
		{
				len = i;
		}
	}
	printf("%d\n", len);

	return 0;
}