백준 14720번 파이썬 풀이: 우유 축제

백준 14720번 우유 축제

 

알고리즘 분류: 그리디 알고리즘, 구현

 

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

 

14720번: 우유 축제

문제

영학이는 딸기우유, 초코우유, 바나나우유를 좋아한다.

입맛이 매우 까다로운 영학이는 자신만의 우유를 마시는 규칙이 있다.

1. 맨 처음에는 딸기우유를 한 팩 마신다.
2. 딸기우유를 한 팩 마신 후에는 초코우유를 한 팩 마신다.
3. 초코우유를 한 팩 마신 후에는 바나나우유를 한 팩 마신다.
4. 바나나우유를 한 팩 마신 후에는 딸기우유를 한 팩 마신다. 

영학이는 우유 축제가 열리고 있는 우유거리에 왔다. 우유 거리에는 우유 가게들이 일렬로 늘어서 있다.

영학이는 우유 거리의 시작부터 끝까지 걸으면서 우유를 사먹고자 한다.

각각의 우유 가게는 딸기, 초코, 바나나 중 한 종류의 우유만을 취급한다.

각각의 우유 가게 앞에서, 영학이는 우유를 사마시거나, 사마시지 않는다.

우유거리에는 사람이 많기 때문에 한 번 지나친 우유 가게에는 다시 갈 수 없다.

영학이가 마실 수 있는 우유의 최대 개수를 구하여라.

입력

첫째 줄에 우유 가게의 수 N이 주어진다. (1 ≤ N ≤ 1000)

둘째 줄에는 우유 가게 정보가 우유 거리의 시작부터 끝까지 순서대로 N개의 정수로 주어진다.

0은 딸기우유만을 파는 가게, 1은 초코우유만을 파는 가게, 2는 바나나우유만을 파는 가게를 뜻하며, 0, 1, 2 외의 정수는 주어지지 않는다.

출력

영학이가 마실 수 있는 우유의 최대 개수를 출력하시오.

 

 

문제 파악

 

이 문제는 딸기 우유는 0, 초코 우유는 1, 바나나 우유는 2로 표현되기 때문에

 

영학이가 사먹을 수 있는 가게는 0 > 1 > 2 > 0 > 1 > 2 … 순으로만 구할 수 있다.

 

예를 들어 0(딸기) 2(바나나) 1(초코) 2(바나나) 순으로 가게가 되있다면

 

영학이는 두번째 바나나 우유를 파는 가게를 들릴 수 없기 때문에

 

영학이가 마실 수 있는 우유의 최대 개수는 3개가 된다.

 

 

코드

 

주어지는 우유 가게의 수는 market 이라는 변수에 저장하였다.

 

우유 가게의 정보는 market_list 라는 리스트에 저장하였다.

 

현재 있는 가게와 다음에 올 가게의 관계를 파악해야 한다.

 

문제에서 0, 1, 2 이외의 정수는 주어지지 않기 때문에 current_milk라는 변수를 만들어서

 

for문 속에서 current_milk 에 1을 더한 수에서 3을 나눈 나머지가 market_list의 인덱스라면

 

영학이가 그 가게에서 우유를 사먹을 수 있기 때문에 count가 올라가게 코드를 짜보았다.

 

처음에 0(딸기 우유)인 가게부터 들려야 하기 때문에 current_milk의 초기값을 -1로 설정하였다.

 

current_milk 가  -1이라면 (current_milk + 1) % 3 이 0이기 때문에

 

market_list의 인덱스가 0일때 영학이가 우유를 사먹기 시작한다.

 

예를 들면 현재 영학이가 있는 가게(current_milk)가 1(초코 우유)라면

 

(current_milk + 1) % 3 이 2인 바나나 우유 가게가 다음에 나와야 count가 올라간다.

 

current_milk 값이 계속 1씩 증가하여도 3으로 나눈 나머지는 0, 1, 2만 나온다.

 

마지막으로 for문이 끝나면 영학이가 마실 수 있는 우유의 최대 개수인 count가 출력된다.