[Greedy] 이코 실전문제

큰 수의 법칙

 

입력 

N(2 ≤ N ≤ 1,000) M(1 ≤ N ≤ 10,000) K(1 ≤ N ≤ 10,000) # K ≤ M 공백으로 구분

N개의 자연수(1 ≤ 자연수 ≤ 10,000) 공백으로 구분

 

출력

특정 인덱스에 해당하는 수가 최대 K번 연속할 수 있을 때, 주어진 자연수들을 M번 더하여 가장 큰 수를 출력.

 

반복되는 수열을 찾아 효율적으로 해결 할 수 있음.

> python

더보기

import sys

n, m, k = map(int, sys.stdin.readline().split())
data = list(map(int, sys.stdin.readline().split()))

data.sort(reverse = True)
first = data[0]
second = data[1]

count = int(m / (k+1)) * k
count += m % (k+1)

result = 0
result += first * count
result += second * (m - count)

print(result)

> java

더보기

import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int m = sc.nextInt();
        int k = sc.nextInt();

        int[] numbers = new int[n];

        for (int i = 0; i < n; i++) {
            numbers[i] = sc.nextInt();
        }

        Arrays.sort(numbers);
        int firstBigNumber = numbers[n - 1];
        int secondBigNumber = numbers[n - 2];

        int count = (m / (k + 1)) * k;
        count += m % (k + 1);

        int result = 0;
        result += firstBigNumber * count;
        result += secondBigNumber * (m - count);

        System.out.println(result);
    }
}

 

---

숫자 카드 게임

 

입력 

N(1 ≤ N ≤ 100) M(1 ≤ N ≤ 100) 공백으로 구분

N개의 줄에 걸쳐 각 카드에 적힌 자연수(1 ≤ 자연수 ≤ 10,000) 공백과 개행으로 구분

 

출력

행의 가장 작은 숫자가 적힌 카드가 선택될 때, 카드에 적힌 가장 큰 숫자 출력

 

각 행의 가장 작은 수만 추출해 그 중 가장 큰 수를 찾을 수 있음.

> python

더보기

import sys

n, m = map(int, sys.stdin.readline().split())

result = 0
for i in range(n):
    data = list(map(int, sys.stdin.readline().split()))
    min_value = min(data)
    result = max(result, min_value)
    
print(result)

>java

더보기

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int m = sc.nextInt();

        int result = 0;

        for (int i = 0; i < n; i++) {
            int min_value = 10001;

            for (int j = 0; j < m; j++) {
                int x = sc.nextInt();
                min_value = Math.min(min_value, x);
            }

            result = Math.max(min_value, result);
        }

        System.out.println(result);
    }
}

---

1이 될 때까지

 

입력 

N(2 ≤ N ≤ 100,000)  K(2 ≤ N ≤ 100,000) # K ≤ N 공백으로 구분

 

출력

N이 1이 될 때 까지 1을 빼거나 K로 나눌 때, 최소 횟수 출력.

> python

더보기

import sys

n, k = map(int, sys.stdin.readline().split())

result = 0
while True:
    if n == 1:
        break
    
    target = (n // k) * k
    result += (n - target)
    n = target
    
    if n < k:
        break
    
    n //= k
    result += 1
    
print(result)

최대한 많이 나누면 최적의 해가 나옴

 

 

while문을 한번 지날 때마다 나누기가 보장되어 시간 복잡도가 log가 됨.

>java

더보기

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int k = sc.nextInt();

        int result = 0;

        while (true) {
            if (n == 1) {
                break;
            }

            result += n % k;
            n = (int)(n / k) * k;

            if (n < k) {
                break;
            }

            result += 1;
            n /= k;
        }

        System.out.println(result);
    }
}

 

---

이것이 코딩 테스트다 _ 나동빈

정리허긔