[Algorithm] 13 강 : 그리디 유형 문제풀이 + 백준 알고리즘 11399번 ATM문제

문제 1. 1이 될 때까지

해당 문제에서 N이 25이고 K가 3일 때 문제를 가정해보자. 

 

1단계 - 첫 번째로 N이 25 일 때는 k로 나눠지지 않는다. 이때는 1로 빼게 된다.  | 25 - 1 =>24

2단계 - 24는 k로 나눠진다. 이때는 k로 나누게 된다. | 24 / 3 =>8

3단계 - 8은 k로 나눠지지 않는다. | 8-1 => 7

4단계 - 7은 k로 나눠 지지 않는다. | 7-1 => 6

5단계 - 6은 3으로 나눠진다 | 6/2 => 2

6단계 - 2는 3으로 나눠지지 않는다 | 2-1 =1

종료

 

이런 방식으로 진행 되게 된다. 

 

이 방식에 대한 정당성 분석을 해봤을 때 가능한 최대한 많이 나누는 작업이 최적의 해를 항상 보장할 수 있는지 봐야 한다. 

 

N이 아무리 큰 수여도, k로 나눈다면 -1을 하는 것보다는 더욱더 빠르게 줄일 수 있다.

 

그래서 가능한 최대한 많이 나누는 작업이 최적의 해를 보장한다. 이것을 코드로 구현하면 아래와 같다.

 

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

result = 0

while True: 				# N이 K로 나누어 떨어지는 수가 될 때 까지 빼기
	target = (n//k)*k 		# 이렇게 공식을 구성함으로 나눠지는 값을 구한다.
    result += (n-target) 	# 나눠지지 않는 값을 result로 뺀다. 이건 1 만큼 단계가 증가됨으로 result에 넣어준다.
    n = target 				# result로 1을 빼는 작업을 하였으니 이제 target의 값을 n으로 변경해주고
      						# N이 k보다 작을 때 (더이상 나눌수 없을때) 반복분을 탈출한다.
    if n < k:
    	break
    result += 1 			# 나눴을때의 단계가 추가되는 것을 구현했다.
    n // = k 				# 여기서 n을 나눈다.

result += (n - 1) 			# 1이 됐을때 체크하는 부분을 위해 -1 을 해준다.
print(result)

 

 

---

 

문제 2, 곱하기 혹은 더하기

 

 

해당 문제에 대해서 아이디어를 내면 대부분의 경우 + 보다는 * 가 값을 크게 만든다.

다만 예외의 경우가 있다. 0 또는 1일 때는 +이 값을 더 크게 만든다. 

따라서 두 수에 대하여 연산을 할 때 두 값이 1 이하인 경우에는 + 로 1 이상인 경우에는 * 로하면 

최적의 해를 구할 수 있다.

 

data = input()

# 첫번째 문자를 숫자로 변경하여 대입

result = int(data[0])

for i in range(1,len(data)):
	# 두 수 중에서 하나라도 '0'혹은 '1'인 경우, 곱하기보다는 더하기 수행
    num = int(data[i])
    if num <= 1 or result <= 1:
    	result += num
    else:
    	result += num

print(result)

 

 

 

---

문제 3. 모험가 길드 

 

 

위와 같이 입력 예시가 있을 때 고려해야 될 것은 공포도 이다.

 

공포도가 1인 모험가는 혼자서 모험이 가능하지만 공포도가 2인 경우에는 2명으로 구성되어야 한다.

 

이걸 고려해서 문제를 풀어야 한다.

 

해당 문제를 풀기 위해서

 

현재 그룹에 포함된 모험가의 수 >= 현재 확인하고 있는 공포도

 

라는 공식이 성립된다. 해당 문제에서는 공포도가 더 커서는 안되기 때문이다.  이것을 코드로 구현하면

 

n = int(input())
data = list(map(int,input().split())
data.sort()

result = 0 # 총 그룹의 수
count = 0 # 현재 그룹에 포함된 모험가의 수

for i in data: # 공포도를 낮은 것 부터 하나씩 확인하며
	count += 1 # 현재 그룹에 해당 모험가를 포함시키디
    if count >= i: # 현재 그룹에 포함된 모험가의 수가 현재의 공포도보다 크거나 같다면 그룹 결성
    	result += 1 # 총 그룹의 수를 증가시키고
        count = 0 #모험가의 수를 초기화 한다.
 
 print(result) # 총 그룹의 수 출력

 

---

 

11399번 문제

 

 

해당 문제에서 신경써야 할 껀 2개정도로 정리되는 것 같다.

하나는 sort를 해야 된 다는 것

두번째는 값을 저장하고 누적해서 더해야 된 다는 것 이였다. 

 

N = int(input())
nums = list(map(int, input().split()))

result = 0
late = 0
if N == 1:
    print(nums[0])
else:
    nums.sort()
    for i in range(N):
            result += (nums[i] + late)
            late += nums[i]
    print(result)

 

위의 내용을 코드로 구현하였다.

 

 

---

이 자료는 동빈 나 님의 이코 테 유튜브 영상을 보고 정리한 자료입니다.

참고 : www.youtube.com/watch?v=m-9pAwq1o3w&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC