Python - 그리디 알고리즘 정복 2탄

그리디 알고리즘 - 숫자 카드 게임

 

숫자 카드 게임의 한 종류로서, 여러 개의 숫자 카드 중에서 가장 높은 숫자가 쓰인 카드 한 장을 뽑는 게임이다.

게임의 룰은 다음과 같다.

 

1. 숫자가 쓰인 카드들이 n x m 형태로 놓여져 있으며, 이때 n은 행의 개수를 의미하며, m은 열의 개수를 의미한다

2. 먼저 뽑고자 하는 카드가 포함되어 있는 행을 선택한다.

3. 그다음 선택된 행에 포함된 카드들 중 가장 숫자가 낮은 카드를 뽑아야 한다.

4. 따라서 처음에 카드를 골라낼 행을 선택할 때, 이후에 해당 행에서 가장 숫자가 낮은 카드를 뽑을 것을 고려하여 최종적으로 가장 높은 숫자의 카드를 뽑을 수 있도록 전략을 세워야한다.

 

즉, 각 행의 숫자에서 가장 작은 값들 중에서, 가장 큰 수를 찾으면 되는 게임이다.

 

예를 들어,

 

3 1 2

5 1 3

3 3 3

 

m은 3(열) 이고, n은 3(행) 이라고 하자.

여기서 카드를 골라낼 행을 고를 때 첫 번째 혹은 두 번째 행을 선택하는 경우, 최종적으로 뽑는 카드는 1이다. 하지만 세 번째 행을 선택하는 경우 최종적으로 뽑는 카드는 3이다. 따라서 다음 예시에서는 세 번째 해을 선택하여 숫자 3이 쓰여진 카드를 뽑는 것이 정답이다.

 

여기서 사용해야될 함수는 리스트에서 가장 작은 원소를 찾아주는 min() 함수이다. 또한 2중 반복문 구조를 사용한다. 구구단과 유사하니깐 참조하자.

 

min 함수

1) 자료형은 동등하게 놓기
e = [3, 'a', 'b', 'c'] 
>> print(min(e)) # error : str 타입과 int 타입은 비교할 수 없기 때문


2) 문자형에서도 가능
b = 'BlockDMask' print(min(b)) 
>> 반환 : 'B'


3) 여러 리스트에서도 사용 가능
# min(arg1, arg2) 함수
 a = [1, 2, 3] b = [4, 5, 6] print(min(a, b)) 
>> 반환 : [1,2,3]


4) 문자열 2개 이상에서도 사용 가능
# min(arg1, arg2) 함수
c = 'BlockDMask'
d = 'BAAAlockDMask' print(min(c, d)) 
>> 반환 : 'B'


5) 튜플에서도 사용 가능
# min(iterable) 함수
d = (6, 5, 4, 2) print(min(d)) 
>> 반환 : 2

 

 

 

 

입력 조건

- 첫째 줄에 숫자 카드들이 놓인 행의 개수 n과 열의 개수 m이 공백을 기준으로 하여 각각 자연수로 주어진다

( 1 <= N, M <= 100 )

- 둘째 줄부터 N개의 줄에 걸쳐 각 카드에 적힌 숫자가 주어진다. 각 숫자는 1 이상 10,000 이하의 자연수이다.

 

출력 조건

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

 

 

 

 

입력 예시 1

3 3

3 1 2

5 1 5

2 2 2

 

출력 예시 1

2

 

입력 예시 2

2 4

8 3 1 8

3 3 3 5

 

출력 예시 3

3 

---

첫번째 코드

 

 

 

 

두번째 코드

 

 

 

 

 

---

2. 그리디 알고리즘 - 1이 될 때까지

 

어떤 수 n이 1이 될 때까지, 다음의 두 과정 중 하나를 반복적으로 선택하여 수행함

두번째 연산은 n이 k로 나누어떨어질 때만 선택 가능함

 

 

1. n에서 1을 뺀다

2. n을 k로 나눔

 

 

n이 13이고 k가 4라고 하면, 1번의 과정을 통해 12가 되고, 2번의 과정을 통해 3이 되고, 1번의 과정을 2번 거치면 1이 된다.

 

즉, 1번x1 + 2번x1 +1번x2 으로 총 4번 반복하게 된다.

 

즉 다음과 같이 알고리즘을 짜야한다.

 

k로 나누어 떨어지는지 or k로 나누어떨어지지 않는지에 따라, 처음에 1을 빼주는 과정이 먼저 실행이 된다.

 

입력 조건 : 첫째 줄에 n(2보다 크고 100,000 보다 작은 수)와 k(2보다 크고 100,000 보다 작은 수)가 공백으로 구분되며, 각각 자연수로 주어진다. 이때 입력으로 주어지는 n은 항상 k보다 크거나 같다.

 

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

 

25 5 => 2

10 7 => 4

 

n, k = map(int, input().split())
result = 0

# N이 K 이상이라면 K로 계속 나누기 10 3
while n >= k:
    # 크게 2가지로 나눌 수 있음 : k로 나누어 떨어지는 경우 or 아닌 경우
    # N 이 K로 나누어 떨어지지 않는다면 N에서 1씩 빼기
    while n % k != 0:
        n -= 1
        result += 1
    # k 로 나눌 수 있는 경우
    n //= k
    result += 1

# n 이 k보다 작아질때는, 1씩 빼주는 카운트
while n > 1:
    n -= 1
    result += 1

print(result)

 

 

(Solution1)

while문 2개 사용하기

 

위의 식처럼 풀 수도 있고, 비슷하지만 다른 풀이도 존재한다.

 

 

(Solution2)

while문 1개 사용하기

# n,k를 공백으로 구분하여 입력받기
n, k = map(int, input().split())
result = 0

while True:
    # (n==k 로 나누어 떨어지는 수)가 될 때까지 1씩 빼기 10 4... 17 3
    target = (n // k) * k  # 8
    result += (n - target) # 10 - 8 = 2
    n = target # 8
    
    # n이 k보다 작을 때(더 이상 나눌 수 없을 때) 반복문 탈출
    if n < k:
        break
    
    # k로 나누기
    n //= k # n은 2
    result += 1

#마지막으로 남은 수에 대하여 1씩 빼기
result += (n-1) # for문을 돌리지 않고도 횟수니깐, 다음과 같이 표현(n-1)
print(result)

 

 

 

---