[백준] 2839-설탕 배달(C++)

문제링크:www.acmicpc.net/problem/2839

2839번: 설탕 배달

 

레전드 문제 설탕배달입니다....ㅋㅋㅋ

입문자분들이 가장 많이 풀고 절망을 느끼는 문제입니다.

오랜만에 다시 풀어봤는데 감회가 새로워서 포스팅합니다.

 

저의 예전 답입니다.

#include <stdio.h>
int main()
{
	int x = 0, y = 0, N = 0, resultx = 0, resulty = 0;
	int i = 0;
	int j = 0;
	scanf("%d", &N);
	for (x = 0; i <= N; x++)
	{
		i = 5 * x;
		for (y = 0; j <= N; y++)
		{
			j = 3 * y;
			if (i + j == N)
			{
				resultx = x;
				resulty = y;
			}
		}
		j = 0;
	}
	if (resultx == 0 && resulty == 0)
		printf("%d\n", -1);
	else
		printf("%d\n", resultx + resulty);
}

이중포문을 사용해서 구현했습니다.

5씩 증가하는 i와 3씩 증가하는 j의 모든 조합을 비교해보며 결과값을 도출하는 방법입니다. i가 j보다 상위 반복문에 있기 때문에 i가 최대가 되는 결과값이 최종적으로 resulty, x 에 저장이 되어지고 이를 통해 결과값을 얻습니다.

 

하지만 만약에 시간이나 데이터 크기가 더욱 커진다면 테스트를 통과하지 못할 확률이 있습니다.

예를 들어서 n=1000,000라면 해당 코드는 O(n^2)이므로 시간제한 1초를 훌쩍 넘게 됩니다.

 

이를 예방하기 위해서  반복문 하나만 써서 해결하는 방식도 생각해봤습니다.

	int answer = 0;
	int mod, num, result;
	num = n / 5;



	while (num >= 0) {

		mod = 0;
		result = 0;

		if (num > 0) {
			mod = n - 5 * num;
			result = num;
		}
		else {
			mod = n;
		}

		result += mod / 3;
		mod = mod % 3;

		if (mod == 0) {
			answer = result;
			return answer;
		}

		num--;

	}
	if (mod != 0)
		return -1;

	
		
	//return answer;

 

사실 같은 원리입니다. while문에서 5로 나눌수 있는 만큼 반복하며 진행합니다. 이때 5로 나눈 나머지만큼 3으로 다시한번 나눠보고 나머지가 0된다면 그대로 바로 결과를 출력하는 구조입니다.

 

사실은 2중포문을 사용할 필요가 없던 코드입니다. 

 

사실 구현하면서 고민을 꽤 많이 했던터라 아직도 많이 부족하다는 것을 느낄 수 있었습니다. 

 

더욱 열심히 해서 알고리즘 마스터가 되겠습니다.