[5문제] 그리디 문제풀이 03

백준 1439번

해결 아이디어

문자열에서 0과 1이 변화될 때, 뒤집는 횟수를 2로 나눈 몫이 결과값과 동일하다는 규칙을 확인했다.
0,1 0번, 길이 1
01: 1번, 길이 2
010: 1번, 길이 3
0101: 2번, 길이 4
01010: 2번, 길이 5
010101: 3번, 길이 6
0101010: 3번, 길이 7

내가 작성한 코드

lst = input()
num = len(lst)
count = 0
for i in range(num-1):
    if lst[i] != lst[i+1]:
        count+=1
print((count+1)//2)

백준 14720번

해결 아이디어

영학이의 규칙은 0,1,2가 반복적으로 나타나야한다는 것이다. 그렇다면 0,1,2가 반복된다는 것은 3으로 나눈 나머지들이 나열되는 것과 같은 것이다.

내가 작성한 코드

num = int(input())
market = list(map(int,input().split()))

count = 0
for i in range(num):
    if market[i] == count % 3:
        count+=1
print(count)

백준 11034번

해결 아이디어

바깥쪽의 두 캥거루가 가운데 캥거루와 수직선 상에서 얼만큼씩 떨어져 있는가를 비교하면 되는 문제였다. 캥거루 사이의 거리가 멀다면 캥거루가 움직일 수 있는 좌표가 많기 때문에 움직일 수 있는 횟수가 자연스럽게 증가하게 된다.

내가 작성한 코드

while True :
  try :
    A, B, C = map(int, input().split())
    distance1 = (B - A) -1
    distance2 = (C - B) -1
    result = max(distance1, distance2)
    print(result)
  except :
    break

백준 22864번

해결 아이디어

하루에 최대로 일을 할 수 있는 경우는 피로도가 M에 도달했을 때 피로도를 0까지 되도록 쉬어주고, 다시 일을 하는 경우가 가장 그리디한 방법이다. 나머지는 구현의 부분이었다.

내가 작성한 코드

A, B, C, M = map(int,input().split())

Fatigue = 0
time = 0
work = 0

if A > M :
    print(0)
    
else:

    while time != 24 :
        time += 1
        
        if Fatigue + A <= M:
            work += B
            Fatigue += A

        else:

            if Fatigue - C > 0:
                Fatigue -= C

            else:
                Fatigue = 0

    print(work)

백준 14487번

해결 아이디어

마을의 수가 n개라면, 원형으로 마을들이 위치하여 있기 때문에 마을 이동은 n-1번만 하면 된다. 따라서 최소 이동 비용은 가장 비싼 이동 비용을 제외한 나머지 마을 이동 비용의 합이 최적의 해가 된다.

내가 작성한 코드

town = int(input())
cost = list(map(int,input().split(' ')))

max_cost = max(cost)

index = cost.index(max_cost)
cost.pop(index)

total = 0

for i in cost:
    total += i
print(total)