(이코테 w/ Python) 그리디 알고리즘 2

문제 2. 1이 될 때 까지

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

 

1. N에서 1을 뺀다
2. N을 K로 나눈다

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

(17 - 1 = 16, 16 / 4 = 4, 4 / 4 =1)

 

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

 

• 입력 조건: 첫째 줄에 N(1 <= N <= 100,000)과 K(2 <= K <= 100,000) 가 공백을 기준으로 하여 각각 자연수로 주어진다. 
• 출력 조건: 첫째 줄에 N이 1이 될 때 까지 1번 혹은 2번의 과정을 수행해야 하는 횟수의 최소값을 출력한다.

<출처: 유튜브 동빈나 채널>

 

문제 해결 아이디어

주어진 N에 대해 최대한 많이 나누기를 수행하면 된다. (나눌 수 있다면 나누고 그렇지 않다면 1을 뺀다)

왜냐하면, N의 값을 줄일 때 2 이상의 수로 나누는 작업이 1을 빼는 작업보다 수를 훨씬 많이 줄일 수 있다. 

 

예를 들어 N = 25, K = 3일 때, 

출처: 유튜브 동빈나 채널

3으로 나누어질 수 있도록 1을 뺀다. 

 

가능한 최대한 많이 나누는 작업이 최적의 해를 항상 보장할 수 있을까?

문제의 조건 상 K가 항상 2 이상의 수 이기 때문에  N이 아무리 큰 수일지라도 K로 계속 나눈다면 빠르게 줄일 수 있다. 

즉, 문제의 조건에 해당하는 N과 K에 대해서 항상 K로 나누는 것이 1을 빼는 것 보다 빠르게 N을 줄일 수 있다. 또한, N은 항상 1에 도달하게 된다. (최적의 해 성립)

 

답안 예시

n, k 두 개의 입력이 공백을 기준으로 바로 입력이 되기 때문에 입력받은 문자열을(input(), split()) 공백 기준으로 나눈 뒤에 map() 함수를 이용해서 각각 int형(정수)로 바뀐 뒤에 n과 k를 넣은 것이다. 

 

while 반복문을 이용해서 n을 줄여보자. 

target 변수에 n을 k로 나눈 몫과 k를 곱한 값을 넣어준다. n을 k로 나누어 떨어지지 않을 경우 가장 가까운 k로 나누어 떨어지는 수가 어떤 것인지 찾고자 할 때 사용할 수 있다. 

즉, n에서 1을 빼는 과정을 몇 번 반복해서 target 값을 만들 수 있고, target 값은 k로 나누어 떨어지는 수가 된다. 

 

result 변수는 연산을 수행하는 횟수를 출력한다. 1을 빼는 연산을 몇 번 수행할지 한 번에 계산해서 넣어준다. 

(n = target) n이 target이 되도록 하였다.  그리하여 n이 k보다 작다면 반복문을 탈출할 수 있도록 한다.

그렇지 않다면 n을 k로 나눌 수 있도록 한다. 

 

n이 1보다 크다면 1이 될 수 있도록 만들기 위해서 남은 수에 1씩 빼는 연산을 한 번에 계산할 수 있도록 만든다.  

 

 

문제 3. 곱하기 혹은 더하기 

출처: 유튜브 동빈나 채널

• 입력 조건: 첫째 줄에 여러 개의 숫자로 구성된 하나의 문자열 S가 주어진다. (1 <= S의 길이 <= 20)
• 출력 조건: 첫째 줄에 만들어질 수 있는 가장 큰 수를 출력한다.

 

문제 해결 아이디어

대부분의 경우 +보다 x가 더 값을 크게 만든다.

다만, 0 혹은 1인 경우 곱하기보다 더하기를 수행하는 것이 더 효율적이다.

두 수에 대해 연산을 수행할 때 두 수 중 하나라도 1이하인 경우는 더하기, 두 수가 모두 2 이상인 경우는 곱하면 된다.

 

답안 예시

(range(1, len(data))): 두번째 숫자부터 차례대로 확인하면서 매번 result 변수의 값과 새로 확인하는 값 사이에서 연산을 수행한다.

result +=: 두 수 중에서 하나라도 1 이하인 경우 즉, 0 혹은 1인 경우 더하기 수행을 하고, 

result *=: 그렇지 않다면 곱하기 수행을 한다.

 

 

문제 4. 모험가 길드

출처: 유튜브 동빈나 채널

예를 들어, N = 5이고, 각 모험가의 공포도는 

 

2 3 1 2 2 

 

이다.

 

그룹 1에 공포도가 1, 2, 3인 모험가를 한 명씩 넣고,

그룹 2에 공포도가 2인 남은 두 명을 넣게 되면 총 2개의 그룹을 만들 수 있다. 

 

몇 명의 모험가는 마을에 그대로 남아 있어도 되기 때문에 모든 모험가를 특정한 그룹에 넣을 필요는 없다. 

 

문제 해결 아이디어

출처: 유튜브 동빈나 채널

앞에서부터 공포도를 하나씩 확인하며 ‘현재 그룹에 포함된 모험가의 수'가 ‘현재 확인하고 있는 공포도'보다 크거나 같다면 이를 그룹으로 설정하면 된다. (모험가 수 >= 공포도) 

공포도가 오름차순으로 정렬되어 있다는 점에서, 항상 최소한의 모함가의 수만 포함되어 그룹을 결성하게 된다. 

 

(네 번째 모험가, 5번째 모험가는 모험가의 수(2)와 공포도(3)보다 낮기 때문에 그룹을 결성할 수 없다. 

 

답안 예시