티스토리 뷰

PS/백준

2839번 설탕 배달

unside 2019. 6. 18. 00:09

백준 2839번

문제 사이트 :
https://www.acmicpc.net/problem/2839


설명 :
처음으로 알고있는 사실은 3킬로그램과 5킬로그램은 각각 1봉지면 가능하다는 사실이다.
그러면 6킬로그램(3+3)과 8킬로그램(3+5 or 5+3) 10킬로그램(5+5)은 3킬로와 5킬로에서 한봉지씩 더한 값이다.
이런식으로 밑에서 부터 하나씩 더해가면서 구해준다.

#include <stdio.h>
int arr[5001];

void Set() {
	for (int i = 0; i < 5001; i++) //-1로 초기화
		arr[i] = -1;

	arr[3] = 1;  arr[5] = 1; //초기값 설정

	for (int i = 3; i < 5001; i++) {
		if (arr[i] == -1) //현재 -1이면 이후값을 구할 수 없기 때문에 continue
			continue;
		if (i + 3 < 5001) { //최대 범위를 넘지않으면
			if (arr[i + 3] != -1) { // 기존값이 존재하면 비교해줌 예시) 8(3+5 or 5+3)
				if (arr[i] + 1 < arr[i + 3]) {
					arr[i + 3] = arr[i] + 1;
				}
			}
			else
				arr[i + 3] = arr[i] + 1;
		}
		if (i + 5 < 5001) {
			if (arr[i + 5] != -1) { // 기존값이 존재하면 비교해줌 예시) 8(3+5 or 5+3)
				if (arr[i] + 1 < arr[i + 5]) {
					arr[i + 5] = arr[i] + 1;
				}
			}
			else
				arr[i + 5] = arr[i] + 1;
		}
	}
}

int main(void) {
	Set();
	int num;
	scanf("%d", &num);
	printf("%d", arr[num]);
	return 0;
}
저작자표시 비영리 동일조건 (새창열림)

'PS > 백준' 카테고리의 다른 글

9498번 시험성적  (0) 2019.06.18
8393번 합  (0) 2019.06.18
2742번 기찍N  (0) 2019.06.17
2741번 N찍기  (0) 2019.06.17
2739번 구구단  (0) 2019.06.17
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
TAG more
«   2025/11   »
일 월 화 수 목 금 토
1
2 3 4 5 6 7 8
9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25 26 27 28 29
30
글 보관함