[c언어] 백준 (14916 거스름돈 / 11720번 숫자의 합 / 2851 슈퍼마리오) ★그리디 알고리즘 / 아스키코드 문자 연산

그리디 알고리즘, 아스키 코드를 활용한 문자의 연산

 

1. 백준 14916번 거스름돈

(실버 5)

https://www.acmicpc.net/problem/14916

14916번: 거스름돈

 

실버 단계이고 그리디 알고리즘 활용 문제인데... 이렇게 푸는게 알고리즘을 활용한건가 싶을만큼 되게 금방 풀렸다..ㅎ

 

코드

#include <stdio.h>

int main()
{
    int count=0; //동전 개수
    int n=0; //거스름돈 금액
    
    scanf("%d", &n);
    
    if(n%5==0) {
        count=n/5;
    } else {
        while(n>0) {
            n-=2;
            count++;
            if(n%5==0){
                count+=n/5;
                break;
            }
        }
    }
    
    if(n<0) {
        printf("-1");
    } else {
        printf("%d", count);
    }
    

    return 0;
}

해설 :

처음 n값이 5의 배수면, 5로 나눈 몫이 답

처음 n값이 5의 배수가 아니면, 5의 배수가 될때까지 n에서 2씩 빼기! 그리고 동전수 +1.

그러다가 n이 음수가 되면 거슬러줄 수 없으므로 -1!

 

간단하다!

 

 

 

그리디 알고리즘이란?

일명 탐욕법, 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓는 것!

 

이 문제가 왜 그리디 알고리즘을 활용한 것인지 서치해보았고, 대충.. 알 것 같다...!

 

 

5로 나누어떨어질 경우가 가장 좋은 답!! 5원짜리 동전을 최대한 많이 써서 동전의 총 개수를 줄여야하므로 :)

즉, 탐욕법으로 쫓을 가장 최적의 상황이 'n이 5의 배수가 되는 것'이기 때문에 나의 풀이 또한 그리디 알고리즘을 활용한 것이다. 

 

 

 

 

 

 

 

 

 

2. 백준 11720번 숫자의 합

(브론즈 4)

https://www.acmicpc.net/problem/11720

11720번: 숫자의 합

 

한 3번 정도 틀렸다.. 자료형 때문에!!

긴 숫자열을 받고, 각 자리수의 합을 구하면 되는 간단한 문제이다.

그러나 오류를 범했다.

 

처음엔 다 정수로 입력받으려 했으나, 숫자열 길이가 좀만 길어져도 오버플로우가 발생하고 쓰레기값이 나왔다. 

문제에서 주어진 숫자열의 최대 길이는 100자였으므로 숫자열을 정수 자체로 받기엔 무리가 있다.

long long int 다 동원해봐도 그냥 문자열로 받아서 연산하는게 훨 낫다. 문자열 연산이 조금 생소할 뿐 ㅎㅅㅎ..

 

즉, 숫자열이 아닌 문자열로 받아서 연산을 해야한다!

 

아스키 코드를 활용한 문자열의 연산

#include <stdio.h>

int main()
{
    int n=0;
    int sum=0;
    
    scanf("%d", &n);
    char num[n];
    
    scanf("%s", num);
    
    for(int i=0; i<n; i++) {
        sum+=(num[i]-48); //문자 0~9를 아스키코드로 변환하면 10진수로 48~57
    }
    
    printf("%d", sum);
    

    return 0;
}

 

아스키코드

아스키 코드. 보라색 부분이 문자 0~9

문자 '0' = 십진수 48

이를 활용해 문제를 해결했다.

 

 

 

 

 

3. 백준 2851번 슈퍼 마리오

(브론즈 1)

https://www.acmicpc.net/problem/2851

2851번: 슈퍼 마리오

 

 

#include <stdio.h>

int main()
{
    int arr[10];
    int score=0;
    int sum=0;
    int index=0;
    int over=0; //제일 처음으로 100점 넘었을 때
    int under=0; //100점 넘기 직전
    
    for(int i=0; i<10; i++) {
        scanf("%d", &arr[i]);
    }
    
    
    while(sum<=100){
        sum+=arr[index];
        index++;
        if(sum==100) {
            score=100;
            break;
        }
        
        
    }
    
    over=sum;
    under=sum-arr[index-1];
        
        
    if((over-100)>(100-under)){
        score=under;
    } else {
        score=over;
    }
            
    
    
    printf("%d", score);
    

    return 0;
}

이건 그냥 간단한건데... 별코인 얻고싶어서 뭐 더 풀까 하다가 이름이 귀여워서 풀어봄. ㅎㅅㅎ 귀여웡