[C++]백준 17174번: 전체 계산 횟수

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

17174번: 전체 계산 횟수

 

1. 문제 설명

 

호근이는 우선 1달러 지폐를 한 장씩 세면서 M개의 지폐를 한 묶음으로 만든다. 그다음에는 새로 만들어진 묶음을 하나씩 세면서 M개의 묶음을 다시 하나로 묶는다. 더 이상 묶음이 만들어지지 않을 때까지 이 과정을 반복한다. 이때 호근이가 묶음을 포함해 지폐를 센 전체 횟수를 구하여라.

예를 들어 N이 13이고 M이 10일 때, 13달러를 세기 위해서는 1달러씩 총 13번을 세고, 지폐 10장을 한 묶음으로 만들고, 한 개의 묶음을 다시 한번 세어 총 14번을 세야 한다.

 

N이 주어졌을 때 처음에는 N개를 전부 센 다음 두번째부터는 M개의 묶음으로 이루어진 묶음의 개수만 세면 된다.

 

따라서 묶여진 묶음의 개수가 M개보다 적어질 때까지 묶음의 개수(N/M)를 더하면 된다.

 

문제의 조건으로 M ≤ N 이 주어졌기 때문에 최소 한번은 하나의 묶음 이상으로 묶이기 때문에 do while문을 사용했지만 다음과 같은 조건이 없다면 while문으로 반복하는 것이 좋을 것 같다.

 

 

2. 코드

 

#include <iostream>

using namespace std;

int main()
{
    int n,m,sum=0;
    
    cin >> n >> m;
    
    sum+=n;
    
    do{
        sum+=n/m;
        n/=m;
    }while(n>=m);
    
    cout << sum <<"\n";
    
    return 0;
}