baekjoon c++ 2839 설탕배달/ 그리디 알고리즘

 

3과 5로 나누어질 때만 잘 출력됐고 3kg, 5kg 봉지를 같이 사용해야 할 때는 출력이 안되서 계속 막혔다

구글링해서 다시 풀어봤다

 

 

 

맨처음에 풀었던 방식

#include <stdio.h>

void main() {

	int N;
	int a, b=0;
	int sum = 0;
	int cnt3;
	int cnt5;

	scanf_s("%d", &N);

	while (1) {
		if (N % 3 == 0 || N % 5 == 0) {
			if (N % 3 == 0) {
				cnt3 = N / 3;
				printf("%d\n", cnt3);
				break;
			}
			else if (N % 5 == 0) {
				cnt5 = N / 5;
				printf("%d\n", cnt5);
				break;
			}
		}
		else {
			N = a + b;

			cnt3 = N / 3;
			cnt5 = N / 5;

			sum = cnt3+cnt5;
		}
			printf("%d\n", sum);
	}



}

 

 

 

---

 

 

다시 풀어본 문제

#include <stdio.h>

int main() {

	int N;
	int a, b=0;
	int remain=0;


	scanf("%d", &N);
	a = N / 5;
	remain = N % 5;

	while (remain > 0) { //설탕을 5로 나눴을 때 나머지가 0보다 클 때 까지 반복

		if (remain < 3 && a>0) {
        //설탕을 5로 나눴을 때 나머지가 3보다 작고, 몫이 0보다 클 때
        
			a--; //나머지가 최소 3이 될 때 까지 5kg봉지를 하나씩 줄인다
			remain += 5; //5kg 봉지가 1개 감소하면, 나머지는 5가 증가한다
		}
		b++; //5kg 봉지를 하나씩 줄이면 3kg 봉지를 하나씩 늘린다
		remain -= 3; //3kg 봉지를 하나씩 늘릴 때 마다, 5kg봉지의 나머지에서 3을 뺀다
	
	}

	if (remain != 0) {
		printf("-1");
	}

	else {
	printf("%d", a+b);

	}

}

5kg 봉지를 최대한 써서 설탕봉지를 적게 들고 가야 함

5kg 봉지를 먼저 사용하고, 나머지는 3kg 봉지로 딱 맞게 채워야 한다