백준 14720 (우유축제) [Python/파이썬] [Greedy/그리디]

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

14720번: 우유 축제

 

---

나:

N = int(input())
stores = map(int,input().split())
order = [0,1,2]
T=0
count =0

while T!=N:
    for i in order:
        for store in stores:
            T +=1
            if i == store:
                count +=1
                break

print(count)

완성된 코드는 위와 같다.

 

(1)
N = int(input())
stores = map(int,input().split())
order = [0,1,2]
T=0
count =0

우선 우유 가게의 수 N을 정수값으로 입력받는다.

그 다음 우유가게들의 정보를 stores 리스트에 담는다. 

방물해야할 우유가게의 순서는 0,1,2 를 만족해야 하기 떄문에 순서정보를 담은 order 리스트 선언.

나중에 사용할 반복문의 종결조건을 만들기 위해 N과 비교할 T 변수를 선언하고 마실 수 있는 우유의 수를 나타낼 count 변수 또한 선언.

 

(2)
while T!=N:
    for i in order:
        for store in stores:
            T +=1
            if i == store:
                count +=1
                break

print(count)

while에 종결조건을 사용함으로 인해 order의 요소들을 끝까지 사용해도 가게를 전부 지나치지 않으면 (T != N ) 다시 반복을 하도록 만들어 마시는 순서의 기준이 되는 order의 요소 2 까지  사용되도 처음 요소인 0부터 다시 반복하도록 만듦

이중 중첩 for 반복문을 이용해 순서의 기준이되는 i 와 제시한 가게정보인 store 가 같으면 마실수 있는 우유의 개수인 count 값이 1 늘어나고 해당 반복문을 종료시켜 바로 다음 순서의 우유정보와 같은지 아닌지 따지기 위해 break 를 사용

이때 순서조건에 부합하지 않아 사마시지  않은 것도 지나간 우유가게의 횟수에 포함되기 때문에 반복문이 실행될 때 마다 T의 값을 한개씩 올린다. 

최종적으로 마실 수 있는 우유의 개수가 담긴 count 변수를 출력한다.

---

다른사람:

n = int(input())
a=list(map(int, input().split()))

milkd = 0
cmilk = 0
for milk in a :
    if cmilk == milk:
        milkd += 1
        cmilk = (cmilk + 1) % 3

print(milkd)

완성된 코드는 위와 같다.

주목해야할 부분은 for 반복문을 두개가 아닌 하나만으로 구현하며 수학적 지식을 활용했기 때문에 시간복잡도가 O(N)으로 줄어들어 가져왔다.

마시는 우유 순서인 0,1,2 를 구현하기 위해 cmilk 변수를 사용했다.

먹어야 하는 순서 cmilk와 현재 가게에서 파는 우유  milk가 같은지 따지고 맞으면 마실 수 있는 우유의 최대 개수를 의미하는 milkd 를 하나씩 올리고  순서기준인 cmilk 값 또한 하나 올리고 다음 먹는 순서 기준으로 바꾼다.

이때 3을 나눈 나머지를 이용해 마시는 것의 마지막 순서인 바나나우유 2까지 마시면 다시 딸기우유 0을 마시는 순서로 바뀌도록 구현한다.