목차
1학기때 C++을 배웠었는데 그 이후로 아예 손을 놓고 있다보니 다 까먹게 생겨서 조금씩 다시 공부해보고자 알고리즘을 해보려고 한다.
내년에 알고리즘 과목도 있기도 하고, 문제 푸는게 재미있기도 하고 겸사겸사이다.
하도 오랜만에 풀어보려고 하니까 어떻게 할지 감이 잘 안와서 전에 풀었던 문제를 다시 풀어보며 해보려 한다.
하루에 한 문제정도만이라도 꾸준히 풀면 좋을텐데... 일단 열심히 해보자.
코드의 개선 할 점 등의 피드백을 환영합니다. 부족한 실력에 공부하는 것을 도와주세요!
문제
상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다.
상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다.
상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N이 주어진다. (3 ≤ N ≤ 5000)
출력
상근이가 배달하는 봉지의 최소 개수를 출력한다. 만약, 정확하게 N킬로그램을 만들 수 없다면 -1을 출력한다.
출처
Contest > Croatian Open Competition in Informatics > COCI 2010/2011 > Contest #7 1번
문제를 번역한 사람: baekjoon
알고리즘 분류
나의 풀이
#include <iostream>
using namespace std;
int main(){
int three=0, five=0;
int n;
int answer = 5000;
cin >> n;
for(int i=n; i>0; i-=5){
five = i / 5;
three = (i % 5 + (n - i))/3;
if((five * 5 + three * 3) == n){
if(five + three < answer) answer = five + three;
}
}
if(answer == 5000) answer = -1;
cout << answer;
}
내가 생각한 풀이
모든 경우의 수를 탐색하는 방식이다.
처음에 5Kg짜리로 모두 채워보고, 그 다음에는 5kg 짜리를 뺀 후 3kg짜리의 개수를 늘려나가 보는 것.
예시)
주어진 무게 N이 18KG 일 때
1회 반복
five = (주어진 무게 - 반복문 횟수 * 5) / 5
= 18 / 5
= 3
five는 (주어진 무게 - 반복문 횟수*5) 에서 5kg의 개수이다.
반복 횟수가 증가할수록 5kg 씩 3kg의 개수의 몫으로 빠져나간다.
three = ((주어진 무게 - 반복문 횟수 * 5) % 5 + (주어진 무게 - (주어진 무게 - 반복문 횟수 * 5))) / 3
= ((18 % 5) + (18 - 18 )) / 3
= 1
three는 5kg가 들어가고 남은 나머지와, 반복횟수가 증가할수록 5kg씩 3kg의 몫으로 빠지는데 이를 합해서 3으로 나눈 개수이다.
즉, 각각의 몫이 딱 떨어진다면
five * 5 + three * 3은 N과 같은 값을 갖게 될 것이고, 이때 five + three의 값이 이전의 개수보다 적다면
좀 더 적은 개수의 봉지로 배달이 가능하다는 뜻이므로 더 적은 개수로 변경해준다.
이 반복을 입력받은 N에서 5씩 빼서 N이 0 미만이 되기 전 까지 해 주면 최종적으로 저장되어있는 봉지의 개수가 답이된다.
five * 5 + three * 3
= 3 * 5 + 1 * 3
= 18
N의 값과 동일하므로 answer은 (five + three)개, 즉 4개가 된다.
이 반복을 입력받은 N에서 5씩 빼서 N이 0 미만이 되기 전 까지 해 주면 최종적으로 저장되어있는 봉지의 개수가 답이된다.
2회 반복
five = (주어진 무게 - 반복문 횟수 * 5) / 5
= 13 / 5
= 2
three = ((주어진 무게 - 반복문 횟수 * 5) % 5 + (주어진 무게 - (주어진 무게 - 반복문 횟수 * 5))) / 3
= ((13 % 5) + (18 - 13 )) / 3
= (3 + 5) / 3
= 2
five * 5 + three * 3
= 2 * 5 + 2 * 3
= 16
주어진 무게와 동일하지 않으므로 answer에 변화는 X
3회 반복
five = (주어진 무게 - 반복문 횟수 * 5) / 5
= 8 / 5
= 1
three = ((주어진 무게 - 반복문 횟수 * 5) % 5 + (주어진 무게 - (주어진 무게 - 반복문 횟수 * 5))) / 3
= ((8 % 5) + (18 - 8 )) / 3
= (3 + 10) / 3
= 4
five * 5 + three * 3
= 1 * 5 + 4 * 3
= 17
주어진 무게와 동일하지 않으므로 answer에 변화는 X
4회 반복
five = (주어진 무게 - 반복문 횟수 * 5) / 5
= 3 / 5
= 0
three = ((주어진 무게 - 반복문 횟수 * 5) % 5 + (주어진 무게 - (주어진 무게 - 반복문 횟수 * 5))) / 3
= ((3 % 5) + (18 - 3 )) / 3
= (3 + 15) / 3
= 6
five * 5 + three * 3
= 0 * 5 + 6 * 3
= 18
주어진 무게와 동일하나, 개수는 0 + 6 = 6 개로 이전의 값인 4보다 크므로 4가 유지된다.
이후 주어진 무게 - 반복문 횟수 * 5 의 값이 0 미만이 되므로 반복문은 종료되고
최종 개수는 4개로 된다.
문제 푸는 시간보다 글 쓰는 시간이 더 오래걸리는 거 같다.
다음번에는 코드를 올리고 내가 어떻게 생각하고 풀었는지에 대해서는 간략하게 작성하는 방향으로 해 봐야겠다.
욕심내서 많이 하려고 하지말고 꾸준히 하자.
하루에 한 문제 풀기. 어제 푼 문제 복기 후 새로운 문제 하나 풀기.
이렇게 살아보자.
'공부 > 백준' 카테고리의 다른 글
| 2775번: 부녀회장이 될테야(백준 C++) (0) | 2020.10.13 |
|---|---|
| 10250번: ACM 호텔(백준 C++) (0) | 2020.10.13 |
| 2869번 : 달팽이는 올라가고 싶다(백준 C++) (0) | 2020.10.13 |
| 1193번: 분수찾기(백준 C++) (0) | 2020.10.13 |
| 2292번: 벌집(백준 C++) (0) | 2020.10.13 |