[항해 99 챌린지 / 이코테] 그리디, 예시문제 (큰 수의 법칙, 숫자카드게임, 1이 될때까지)

그리디 알고리즘 이란

(욕심쟁이 알고리즘, Greedy Algorithm)이란 "매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자"라는 모토를 가지는 알고리즘 설계 기법이다.

다만, 해당 알고리즘을 쓸 때 정말 이게 전체적인(종합적으로) 해답이 될 수 있는가 고민해야 한다.

일부 경우는 그게 최적값이 될 수 있지만, 아닐 수 있기 때문이다.

예시문제

---

문제 01 큰수의 법칙

큰 수의 법칙이란 다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙이다.
단, 배열의 특정한 인덱스에 해당하는 수가 연속해서 K번을 초과해 더할 수는 없다.

입력
배열의 크기 N, 숫자가 더해지는 횟수 M, 연속해서 숫자를 최대로 더할 수 있는 횟수 K

출력
큰 수의 법칙에 따라 더해진 답

예시

• 순서대로 2, 4, 5, 4, 6으로 이루어진 배열이 있을 때 M=8, K=3이라고 가정하자. 특정한 인덱스의 수를 연속해서 3번까지 더할 수 있으므로 큰 수의 법칙에 따라 결과는 6+6+6+5+6+6+6+5=46이 된다.
• 다른 예시로 3, 4, 3, 4, 3으로 이루어진 배열이 있을 때 M=7, K=2라고 가정하면, 결과는 4+4+4+4+4+4+4=28이 된다. (다른 인덱스의 4이기 때문에 계속 4를 더할 수 있다)

 

풀이과정

 '특정한 인덱스에 해당하는 수' 이 말이 뭔지 빠르게 생각을 못했는데, 예시를 뚫어지게 쳐다보니.. 각 수의 최대 연속 가능 횟수였다.

그리고 제약조건에 인덱스가 다르면 다른 수라고  이미 정의했으므로, 상위 두개의 원소만 뽑아서 규칙에 따라 더해주면 된다.

N, M, K = map(int,input().split()) #배열 크기, 가능한 항의 수, 각 수의 최대 연속 가능 횟수
arr = sorted(list(map(int,input().split())), reverse=True)
arr = arr[0:2] # 제약조건이 인덱스가 다르면 다른 숫자로 본다 이기 때문에 결국 큰거 두개만 쓰임
ans = 0
mx = arr[0]
term = 0
while(term < M):
    for i in range(0, 2):
        if(term >= M): break
        item = arr[i]
        if(item == mx):
            k = 0
            if(M - term >= K): k = K
            else: k = M - term 
            ans += item * k
            term += k
        else:
            ans += item
            term += 1
print(ans)

 

 

---

문제 02 숫자 카드게임

숫자 카드 게임은 여러 개의 숫자 카드 중에서 가장 높은 숫자자가 쓰인 카드 한 장을 뽑는 게임이다. 단, 게임의 룰을 지키며 카드를 뽑아야 하고 룰은 다음과 같다.
1. 숫자가 쓰인 카드들이 N X M 형태로 놓여 있다. 이때 N은 행의 개수를 의미하며, M은 열의 개수를 의미한다.
2. 먼저 뽑고자 하는 카드가 포함되어 있는 행을 선택한다.
3. 그다음 선택된 행에 포함된 카드들 중 가장 숫자가 낮은 카드를 뽑아야 한다.
4. 따라서 처음에 카드를 골라낼 행을 선택할 때, 이후에 해당 행에서 가장 숫자가 낮은 카드를 뽑을 것을 고려하여 최종적으로 가장 높은 숫자의 카드를 뽑을 수 있도록 전략을 세워야 한다.
카드들이 N X M 형태로 놓여 있을 때, 게임의 룰에 맞게 카드를 뽑는 프로그램을 만드시오.

입력

• 첫째 줄에 숫자 카드들이 놓인 행의 개수 N과 열의 개수 M이 공백을 기준으로 하여 각각 자연수로 주어진다. (1<=N,M<=100)
• 둘째 줄부터 N개의 줄에 걸쳐 각 카드에 적힌 숫자가 주어진다. 각 숫자는 1 이상 10,000 이하의 자연수이다.

출력

• 첫째 줄에 게임의 룰에 맞게 선택한 카드에 적힌 숫자를 출력한다.

풀이과정

아.. 이것도 문제를 이해하는데 시간이 더 걸렸다 ㅋㅋ 이제 행을 선택한다는게 어떤 말이지?? 생각했는데, 게임이니까.. 이기기 위해 최선의 수를 둬야하기 때문에, 선택 가능한 행들 중 가장 최소값이 큰 행에서 카드를 뽑게 하란 거였다.

 

# 행 단위 최소값이 가장 큰 카드
n, m = map(int, input().split())
ans = -1
for _ in range(0, n):
    item = sorted(list(map(int, input().split())), reverse=False)
    ans = max(ans, item[0])
print(ans)

 

---

문제 03 1이 될때까지

어떤 수 N이 1이 될 때 까지 두 과정 중 하나를 반복적으로 선택해 수행한다
- N에서 1을 뺀다.

- N을 k로 나눈다. (N이 K로 나누어 떨어질 때만 가능)

N이 1이 될 때 까지 1번 혹은 2번의 과정을 수행해야하는 최소 횟수를 구하는 프로그램을 작성한다

입력

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

출력

• N이 1이 될때까지 수행해야 하는 연산 횟수의 최소값을 출력한다.

풀이과정

수를 최대한 크게 줄여나가는 방법이 무엇일까 생각해보니 최대한 가능하면 나누기 먼저 하고, 그게 안되면  -1 을 하는 식으로 구현했다.

n, k = map(int,input().split())
cnt = 0
while(n != 1):
    if(n % k == 0 and n > 1):
        n //= k
    else:
        n -= 1
    cnt += 1
print(cnt)