[Python] 그리디 문제 풀이 정리

 

https://www.acmicpc.net/problem/14916

# 내 풀이
n = int(input())

if n%2==0:
    if (n%5)%2!=1:
        t = n//5
        n%=5
        k = n//2 # k는 2원 개수
        n%=2
    else:
        t = (n-5)//5
        n = (n-5)%5 + 5
        k = n//2 # k는 2원 개수
        n%=2
elif n>3:
    if n==5:
        n%=5
        t = 1
        k=0
    else:
        n-=5
        t = 1
        k = n//2 # k는 2원 개수
        n%=2
        while k>=5:
            t+=2
            k-=5

    
if n!=0:
    print(-1)
else:
    print(t+k)
# print(t, k)

• 경우의 수를 나눈다.
• n이 짝수일때, n이 홀수일때, 또한 n이 5이상일때 등등...
• n이 홀수면 5를 먼저 빼서 짝수로 바꿔주고(5의 개수 +1) n이 짝수면 2의 동전개수로 모두 바꿔준 다음 2동전 5개와 5동전 2개를 교환하는 형식(while문)

# 다른 풀이
n = int(input())

cnt = 0
i = 0
while True:
    if n % 5 == 0:   # 5의배수이면 or 2로만 거슬러주고 n이 0이된경우 
        cnt += n//5		#5로나눈 몫이 정답 
        break
    else:
        n -= 2   #5의배수가 아니면 2백원씩 뺴면서 5로 나누어떨어지는것이 나오도록
        cnt += 1

    if n < 0:  # 2백원씩 뺏더니 음수가 되버린경우 --> 거슬러줄수 없을을 의미함 
        break
if n<0:			# 음수면 거슬러줄수없 
    print(-1)			
else:
    print(cnt)

• 그냥 while문 안에 집어넣어서 하나씩 계산하는것이 더 좋은 듯. 🥲

 

https://www.acmicpc.net/problem/1449

# 정답 풀이
N, L = map(int, input().split())
data = list(map(int, input().split()))
data.sort()
k = data[0] # 처음 테이프를 붙일 위치

cnt = 1

for loc in data[1:]:
    if loc in range(k, k+L): # 다음 물이 새는 위치가 테이프 길이 내에 존재
        continue 
    else:
        cnt +=1 # 새 테이프 추가
        k=loc # 새 테이프는 새로운 물이 새는 위치에

print(cnt)

• 문제 해석도 못했당ㅎ
• 데이터를 오름차순으로 정렬한 후 sub problem으로 가장 앞의 물이 새는 곳을 막고, 해당 테이프로 다음 물이 새는 곳까지 막을 수 있는가.
• sub problem의 해가 전체 해이다.
• 0.5cm는 따로 고려 안해도 된다. python에서 range는 K<=i<K+L 이므로...

https://www.acmicpc.net/problem/1080

N, M = map(int, input().split())
A = []
B = []
cnt =0

for _ in range(N):
    A.append(list(input()))

for _ in range(N):
    B.append(list(input()))

def reverse(i, j): # 행렬 연산 함수
    for a in range(i,i+3):
        for b in range(j, j+3):
            if A[a][b]=='0':
                A[a][b]='1'
            else:
                A[a][b]='0'


for i in range(0, N-2):
    for j in range(0, M-2):
        if A[i][j]!=B[i][j]:
            reverse(i, j)
            cnt +=1

if A==B:
    print(cnt)
else:
    print(-1)

• A행렬을 0,0부터 B와 비교하며 연산을 계속해주면 된다.
• 이렇게 바꾼 부분 최적해가 전체 최적해가 된다.
• 3X3 연산인 것에 주목하자.

 

https://www.acmicpc.net/problem/1343

# 정답 풀이
board = input()

board = board.replace("XXXX", "AAAA")
board = board.replace("XX", "BB")

if 'X' in board:
    print(-1)
    
else:
    print(board)

• 풀이가 너무 쉽다...괜히 어렵게 함 ㅜ
• python의 replace() 함수를 쓸 때 더 길이가 긴 AAAA를 먼저 사용하도록 한다.

 

https://www.acmicpc.net/problem/2847

N = int(input())
A = []
for _ in range(N):
    A.append(int(input()))
cnt = 0

for i in range(N-1, 0, -1):
    while A[i]<=A[i-1]:
        A[i-1]-=1
        cnt += 1

print(cnt)

• 뒤에서부터 현재 점수와 이전 레벨 점수를 비교해 이전 점수를 깎는다.

 

https://www.acmicpc.net/problem/15903

N, M = map(int, input().split())
A = list(map(int, input().split()))

A.sort()
for _ in range(M):
    A.sort()
    num = A[0]+A[1]
    A[0] = num
    A[1] = num

print(sum(A))

• 매 반복마다 리스트를 정렬해 가장 작은 수(덮어 쓴 수 포함)가 앞에 오도록 해야 함.

 

https://www.acmicpc.net/problem/11501

# 내 풀이
N = int(input())
for _ in range(N):
    day = int(input())
    A = list(map(int, input().split()))
    max_list = []
    for i in range(day):
        A.append(A[i+1:])
    ans = 0

    for i in range(day-1):
        if max(A[i+1:]) > A[i]:
            ans+=max(A[i+1:]) - A[i]
    print(ans)

• 시간 초과!
• max배열 만들어서 주식 최대값도 저장해 최대한 줄여봤는데...현재 인덱스 이후의 max()를 계속 돌리는 건 무리임.

#  정답 풀이
T = int(input())

for t in range(T):

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

    money = 0 # 이익

    maxPrice = 0 # 주식의 최대 가격
    for i in range(len(price)-1, -1, -1):
        if price[i] > maxPrice:
            maxPrice = price[i]
        else: # 현재 가격이 현재 최대 가격보다 작다면 차익 실현
            money += maxPrice - price[i]

    print(money)

• 뒤에서부터 계산하면 굳이 인덱스 슬라이싱으로 max값을 구할 필요가 없구나..!

https://www.acmicpc.net/problem/16435

N, L = map(int, input().split())
h = list(map(int, input().split()))
ans = L
h.sort()
for i in range(N):
    if ans>=h[i]:
        ans+=1

print(ans)

 

 

---

# 회고

 

너무 복잡하게 생각할수록 더 어려워지는 것 같다. 

그리디는 정렬/슬라이싱/뒤에서부터 탐색 등을 적극적으로 활용해봐야 할듯?

 

풀이1은 실버, 풀이2는 골드 문제로 풀려고 하는데 풀이 2를 할 수 있을지 모르겠당ㅎ