[알고리즘] 이코테 그리디 문제풀이 - 파이썬

오늘은 이코테2021 2.그리디 & 구현강의을 들으면서 개념과 기본적이 세문제만 풀어보았습니다. 인턴 퇴근 후 너무 피곤해서 계속 졸면서 했는데 얼른 익숙해져야겠습니다ㅜ

 

https://www.youtube.com/watch?v=2zjoKjt97vQ&t=1136s 

 

1. 1이될때까지

풀이코드) 

from sys import stdin

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

result = 0

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

# 마지막으로 남은 수에 대하여 1씩 빼기
result += (n-1)
print(result)

 

2.곱하기 혹은 더하기

풀이코드)

from sys import stdin

s = stdin.readline()

s_list = list(map(int, s.strip()))

result = s_list[0]
for i in range(1, len(s_list)):
    if s_list[i-1] == 0 or s_list[i-1] == 1:
        result = result + s_list[i]
    elif s_list[i-1] != 0:
        result = result * s_list[i]

print(result)

 

3. 모험가길

풀이코드)

from sys import stdin

n = int(stdin.readline())

n_list = list(map(int, stdin.readline().split()))
n_list.sort() # 오름차순 정렬

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

# 현재 그룹에 포함된 모험가의 수가 현재 확인하고 있는 공포도보다 크거나 같다면 이를 그룹으로 설정
# => 공포도가 오름차순으로 정렬되어 있다는 점에서, 항상 최소한의 모험가의 수만 포함하여 그룹을 결성하게 된다.
for i in n_list:
    count += 1
    if count >= i:
        result += 1
        count = 0

print(result)

 

첫번째 문제와 세번째 문제는 뻘짓을 너무한 코드라.. 정답 코드를 보면서 연습했습니다.