[c++ | 백준] 15311번 약 팔기

c++ 문제 풀이

 

 

 

 

 

 

---

 

 

[백준 15311번 약 팔기 문제]

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

 

 

 

 

---

 

 

 

전체 풀이 코드

#include <iostream>
using namespace std;

int main(void)
{
    cout << 2000 << "\n";
    for (int i = 0; i < 1000; ++i)
        cout << 1 << ' ';
    for (int i = 0; i < 1000; ++i)
        cout << 1000 << ' ';
    return 0;
}

 

 

 

풀이 설명

 

1. 2000개의 약봉지로 100만개의 약 담기

문제에서는 최대 2000개의 약봉지를 사용해서 동규가 원하는 100만개 이하의 약을 줘야한다고 합니다.

즉 2000개의 약봉지를 이용해서 100만이라는 숫자를 만들 수 있어야 하는데, 이를 해결하기 위해서 100만이라는 숫자에 주목해 봅시다.

 

먼저 100만은 1000^2 입니다. 따라서 약봉지 1000개를 1000개의 약으로 채워 넣으면 일단 100만이라는 숫자를 만들 수 있게 됩니다.

하지만 1, 10, 100의 자리 숫자를 커버하지 못하고 1000의 배수가 되는 수만 만들 수 있기 때문에 이를 커버하기 위해서 나머지 1000개의 약봉지에 1개의 약을 담으면 됩니다.

 

이렇게 되면 동규가 요구하는 약의 개수 만큼 1000개가 담긴 약봉지를 집은 후, 나머지 1, 10, 100의 자리를 1개가 담긴 약봉지로 커버하면 모든 수를 만들 수 있게 됩니다.

 

 

---

 

 

이렇게 백준 15311번 문제를 풀이해보았습니다.

궁금한점 있으시면 댓글 남겨주세요!