221110 EC.crew : 그리디 알고리즘

[ 2022년 11월 10일 정모 문제 풀이 모음 ]

 

https://junggoldchae-coding.tistory.com/entry/%F0%9F%A7%9A%E2%80%8D%E2%99%82%EF%B8%8F%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%F0%9F%A7%9A%E2%80%8D%E2%99%82%EF%B8%8F-%EA%B7%B8%EB%A6%AC%EB%94%94-1

 

#1.

해결

동전 0 (백준 11047번)

#include <stdio.h>

int main()
{
    int n,k;
	int ans=0;
    int count=0;
    scanf("%d", &n);
    scanf("%d", &k);

    int arr[n];
    
    for(int i=0; i<n; i++) {
        scanf("%d", &arr[i]);
    }
    
    
    //뒤에서부터 훑어서 작아지는 순간 선택
    int j=n-1;

    while(ans!=k) {
        if(arr[j]<=k-ans) {
            ans+=arr[j];
            count++;
            j=n-1;
        } else {
            j--; 
        }
        
    }
    
    printf("%d", count);
    
    return 0;
}

 

 

 

#2.

해결(백준 시간 초과... 배열 정렬하는 게 너무 오래걸리나봐...)

카드 정렬하기 (백준 1715번)

#include <stdio.h>

int main()
{
    int n;
    int temp=0;
    int sum=0;
    
    int result=0;
    
    scanf("%d", &n);
    
    //가장 작은 2개 고르고 그 둘의 합을 새로 저장.
    //그리고 남은 한 자리는 0으로 초기화.
    
    int arr[n];
    
    for(int i=0; i<n; i++) {
        scanf("%d", &arr[i]);
    }
    
    
    int arrSum=0; 
    
    int x=0;
    
    while(x<n-1) {
        sum=0;
        /*
        //배열이 모두 0되면 종료!
        for(int i=0; i<n; i++) {
            arrSum+=arr[i];
        }*/
        
        sum=arr[x]+arr[x+1]; 
        
        result+=sum;
        
        //0과 두 수의 합으로 배열 재정렬
        arr[x]=0;
        arr[x+1]=sum;
        
        //오름차순 재배열
        for(int i=0; i<n; i++) {
            for(int j=i+1; j<n; j++) {
                if(arr[i]>arr[j]) {
                    temp=arr[i];
                    arr[i]=arr[j];
                    arr[j]=temp;
                }
            }
        }
        
        //printf("%d %d %d\n", sum, x, result);
        x++;
        
    }
    
    printf("%d", result);
    
    
    return 0;
}