[이코테/Python] 1장 그리디 - 1이 될 때 까지

문제

어떠한 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 한다. 단, 두 번째 연산은 N이 K로 나누어떨어질 때만 선택할 수 있다.

1. N에서 1을 뺀다.

2.N을 K로 나눈다.

예를 들어 N이 17, K가 4라고 가정하자. 이때 1번의 과정을 한번 수행하면 N은 16이 된다. 이후에 2번의 과정을 두번 수행하면 N은 1이 된다. 결과적으로 이 경우 전체 과정을 실행한 횟수는 3이된다. 이는 N을 1로 만드는 최소 횟수이다.

N과 K가 주어질 때 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 최소 횟수를 구하는 프로그램을 작성하시오.

 

입력조건

첫째줄에 N(2 <= N <= 100000)과 K(2 <= K <= 100000)가 공백으로 구분되며 각각 자연수로 주어진다. 이때 입력으로 주어지는 N은 항상 K보다 크거나 같다.

 

출력조건

첫쨰 줄에 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 횟수의 최솟값을 출력한다.

 

입력예시 

25 5

 

출력예시 

2

 

untillOne.c

#include <stdio.h>
int main(){
    int n, k;
    int count = 0;
    
    scanf("%d %d",&n, &k);
    
    for(;1;){
        if(n == 1){
            break;
        }
        else if(n % k ==0){
            n /= k;
            count++;
        }
        else{
            n--;
            count++;
        }
    }
    
    printf("%d",count);
}

이번 문제는 딱히 까다로운 조건도 없고 이해하기 어려운 문제도 아니다.

단지 한가지 주의해야될 점은 뺄셈보다 나눗셈을 먼저 해야한다는 것이다.

나눗셈을 했을때 나누어 떨어지지 않는다면 일단 1을 빼야된다.

또한 반복문을 무한으로 돌려야한다.

 

다음은 이코테에서 제공하는 코드이다.

untillOne.py

# N, M을 공백을 기준으로 구분하여 입력 받기
n, m = map(int, input().split())

result = 0
# 한 줄씩 입력 받아 확인하기
for i in range(n):
    data = list(map(int, input().split()))
    # 현재 줄에서 '가장 작은 수' 찾기
    min_value = 10001
    for a in data:
        min_value = min(min_value, a)
    # '가장 작은 수'들 중에서 가장 큰 수 찾기
    result = max(result, min_value)

print(result) # 최종 답안 출력

 

untillOne.cpp

#include <bits/stdc++.h>

using namespace std;

int n, m;
int result;

int main() {
    // N, M을 공백을 기준으로 구분하여 입력 받기
    cin >> n >> m;

    // 한 줄씩 입력 받아 확인하기
    for (int i = 0; i < n; i++) {
        // 현재 줄에서 '가장 작은 수' 찾기
        int min_value = 10001;
        for (int j = 0; j < m; j++) {
            int x;
            cin >> x;
            min_value = min(min_value, x);
        }
        // '가장 작은 수'들 중에서 가장 큰 수 찾기
        result = max(result, min_value);
    }

    cout << result << '\n'; // 최종 답안 출력
}