[C/C++] 나동빈 볼링공 고르기, Greedy
문제 A, B 두 사람이 볼링을 치고 있다. 두 사람은 서로 무게가 다른 볼링공을 고르려고 한다. 볼링공은 총 N개이며 각 볼링공마다 무게가 적혀있고 공의 번호는 1번부터 순서대로 부여된다. 같은 무게의 공이 두 개 있을 수 있지만 서로 다른 공으로 간주한다. 볼링공의 무게는 1부터 M까지의 자연수 형태로 존재한다. 이때 두 사람이 서로 다른 볼링공을 고르는 경우의 수를 구하라. 예를 들어 볼링공이 5개이고 각 볼링공이 번호 순서대로 1, 3, 2, 3, 2라면, 경우의 수는 8이다. 코드 #include #include using namespace std; int main() { int N, M, num, result = 0; int B[11] = { 0 }; scanf_s("%d %d", &N, &M..
2023. 2. 7.
[C/C++] 나동빈 만들 수 없는 금액, Greedy
문제 동빈이는 N개의 동전을 가지고 있다. N개의 동전의 단위(1,000,000이하의 자연수)를 입력받고, 이 N개의 동전을 조합하여 만들 수 없는 정수 중 최솟값을 구하라. 예를 들어 N=5이고 각 단위가 3, 2, 1, 1, 9일 때 만들 수 없는 정수의 최소 단위는 8이다. (N은 1,000보다 작거나 같은 자연수) 코드 #include #include #include #include using namespace std; int main() { vector coin; int N, num, result=1; cin >> N; for (int i = 0; i > num; coin.push_back(num); } sort(coin.begin(), coin.end()); nu..
2023. 2. 7.
[C/C++] 나동빈 1이 될 때까지, Greedy
문제 어떤 수 N이 1이 될 때까지 다음의 두 과정을 반복적으로 선택하여 수행하려 한다. 1. N-1 2. N÷K (단, N이 K로 나누어 떨어질 때) 예를 들어, N이 17일 경우 1번, 2번, 2번 차례로 수행하면 N은 1이 되며, 총 연산횟수는 3이다. N과 K가 주어질 때 연산 횟수를 최소화하여 N을 1로 만드는 프로그램을 작성하라. 첫째 줄에 N(1≤N≤100,000)과 K(1≤K≤100,000)가 주어지며 N은 항상 K보다 크거나 같다. 코드 #include #include using namespace std; int main() { int N, K, num = 0; cin >> N >> K; if (K == 1) { cout
2023. 2. 2.