이번에 저번에 포스팅했던 OS에서 잠시 나와서, 코드 감각이 떨어지면 안되니 한번 문제 풀어보았습니다.
문제는
백준 2839 설탕배달
백준 11047 동전 0
백준 1237 정ㅋ벅ㅋ
백준 2753 윤년
이렇게 4문제를 풀어보았습니다.
어려운 문제는 아니므로, 코드부터 쭉 정리 해 보겠습니다.
*설탕배달
#include <stdio.h>
#include <stdlib.h>
int function(int N);
int count = 0;
int main() {
int N;
scanf("%d", &N);
printf("%d",function(N));
}
int function(int N) {
if (N % 3 == 0 && N%5 != 0) {
while (1) {
if (N == 0) break;
if (N % 5 == 0) {
count = (N / 5) + count;
N = 0;
}
else {
N = N - 3;
count++;
}
}
return count;
}
if (N % 5 == 0) {
count = N / 5;
return count;
}
else {
while (1) {
if (N <= 0) break;
if (N % 5 == 0) {
count = count + N / 5;
N = 0;
}
else {
N = N - 3;
count++;
}
}
if(N == 0) return count;
}
return -1;
}코드 구성은 이렇게 되어있습니다.
풀이과정을 보여드리자면,
1 = -1
2 = -1
3 = 1 3 1개
4 = -1
5 = 1 5 1개
6 = 2 3 2개
7 = -1
8 = 2 5 1개 3 1개
9 = 3 3 3개
10 = 2 5 2개
11 = -1
12 = 4 3 4개
13 = 3 5 2개 3 1개
14 = -1
15 = 3 5 3개
16 = -1
17 = 5 5 1개 3 4개
18 = 4 5 3개 3 1개
19 = -1
20 = 4 5 4개
21 = 5 5 3개 3 2개
22 = -1
23 = 5 5 4개 3 1개
24 = 6 5 3개 3 3개
27 = 3 4개 5 3개
1) 3의배수는 무조건 3이 들어간다
2) 5의 배수는 무조건 5의배수로 끝낸다
3) 그 외는 5로 최대한 줄인 뒤, 3으로 끝낸다.
이렇게 가정과 풀이방법을 세우고 풀었습니다.
제가 그리디를 배울 때, 항상 가정을 많이하고 최적의 풀이방법을 찾으라고 배웠기 때문에 여러가지 상황을 가정하고 문제를 풀이하였습니다.
그래서 결론으로 밑에 3가지로 나누었습니다.
그대로 코드로 조건문을 걸어서 하니까 정답이 잘 나왔습니다.
다음문제는 동전 0 입니다.
#include <stdio.h>
#include <stdlib.h>
int function(int *arr, int K);
int main() {
int N,K;
int *arr;
scanf("%d %d",&N,&K);
arr =(int *)malloc(sizeof(int) *N);
for(int i = N-1; i>=0; i--) {
scanf("%d",&arr[i]);
}
printf("%d\n",function(arr,K));
}
int function(int *arr, int K) {
int count = 0;
int i = 0;
while(1) {
if(K==0) break;
count = count + K/arr[i];
K = K - (arr[i] *(K/arr[i]));
i++;
}
return count;
}이건 어렵지 않았습니다.
제가 C++언어를 써서 풀었더라면, 가변길이배열 인 벡터를 사용해서 풀었을 것 입니다.
하지만 C언어이므로, 배열 공간을 크게 할당하는 것 보다, 필요 한 만큼의 배열만 선언 해 주면 되므로 필요없는 수납공간이 생김을 방지하기위해 동적할당을 하여 문제를 풀었습니다.
그리고 배열안에 넣어줄때는, 가장 큰 금액부터가 0번배열로 시작해서 N-1번째 배열까지 값을 들어가게 하였습니다.
이유는, 토탈 금액에서 가장 최적의 금액의 카운터를 세려면, 입력 한 금액보다 작은 배열안의 값중 큰 값을 선택하여 나누는 것이 가장 최적이기 때문입니다.
그래서 코드로 옮긴 결과, 정답이 잘 나옵니다.
다음은 정ㅋ벅ㅋ 입니다.
이 문제는 소스코드를 공개하지 않겠습니다. 왜냐하면 정말로 짧은 소스길이 이며, 넌센스와 가까운 문제인 기초문제입니다. 문제를 얼마나 잘 이해하고 파악하느냐를 요구하는 문제이며, 프로그래밍의 실력을 많이 요구하는 문제는 아니었습니다.
다음 문제는 윤년 입니다.
#include <stdio.h>
int function(int N);
int main() {
int N;
scanf("%d",&N);
printf("%d",function(N));
}
int function(int N) {
if(N%400 == 0) return 1;
else if(N%100 != 0 && N%4 == 0) return 1;
else return 0;
}윤년의 조건 4의배수이거나, 100배수가 아닌 또는 400의 배수인 년도 입니다.
그러므로 처음에 살짝 고민해보았습니다. 2000년 이라고 가정하고, 이 친구는 400의 배수이므로 윤년입니다. 1900년은 100의 배수이므로 윤년이 아닙니다.
잘 생각해보면 100과 400은 애초에 4의 배수입니다.
그러므로 고려를 해 줄때, 가장 큰 400을 기준으로 입력 한 값을 나머지 연산자로 비교해서 400의 배수에서 나올 수 있는 경우의 수(윤년O 윤년X) 를 찾은 다음, 문제 조건 그대로,
4의 배수이면서 100의 배수가 아닌 얘가 윤년이면 1값 리턴, 아니면 0값 리턴해서
모든 경우의 수와 예외를 다 처리해주시면 쉽게 풀 수 있습니다.
코드의 결과 정상적으로 정답이라고 나옵니다.
쉬운 4문제였지만, 처음 접하면 생각보다 고민해야 할 시간이 긴 문제입니다. 그렇지만 고등한 지식을 요구한 문제가 아니므로 프로그래밍이 어색해질때쯤 풀어보면 감찾기 좋은 문제인 것 같습니다.
