[백준(BOJ)] 11047번 : 동전 0 - C++[CPP]

www.acmicpc.net/problem/11047

11047번: 동전 0

 

---

 

⊙ 문제

⊙ 입력

⊙ 출력

⊙ 예제 입출력

⊙ 알고리즘 분류

• 그리디 알고리즘

 

---

 

⊙ 문제 접근 과정

 

조건에서 입력도 무작위가 아닌 친절하게 오름차순으로 정렬하여서 입력하라고 한다.

 

막힘없이 코드를 작성했고 예제 입출력과 같은 값을 출력할 수 있었다.

하지만 틀렸다고 떴다. 아래 코드이다.

 

#include <iostream>

using namespace std;

int main() {
    int N,K;
    int count = 0;
    cin >> N >> K;

    int money[N];
    for (int i =0; i<N;i++) {
        cin>>money[i];
    }

    for (int i =N; i>0;i--) {
        if (money[i]<=K) {
            K-=money[i];
            count++;
        }
    }

    cout << count;
}

예제 입출력 1, 2번 전부 값이 바르게 나왔다.

하지만 틀렸다. 예외가 존재한다는 말이다.

 

N=1, K=1, Ai=1이면 count 값이 0이 나온다. 그리고 마이너스 인덱스가 나올 수도 있는 코드이다.

 

그래서 int 배열이 아닌 vector로 수정하여 다시 접근했다.

push와 pop을 이용하여 인덱스를 사용하지 않고 반복문을 돌려서 값을 도출했다.

무한 반복문을 돌리고 break로 탈출하게 했다.

 

---

 

⊙ 문제 풀이

 

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int N,K;
    int count = 0;
    cin >> N >> K;

    int a[N];
    vector<int> money;
    for (int i =0; i<N;i++) {
        cin>>a[i];
        money.push_back(a[i]);
    }

    for (;;) {
        while(money.back() <=K) {
            K-=money.back();
            count++;
        }
        money.pop_back();

        if(K==0)
            break;
    }

    cout << count;
}

---

⊙ 결과

 

 

---

⊙ 마무리

 

 

NONE

 

좋아요는 로그인하지 않아도 누를 수 있습니다!