[백준] 우유축제 - 14720번

 

우유 축제

 

1 초

256 MB

7609

4512

4003

61.115%

문제

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

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

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

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

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

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

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

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

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

입력

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

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

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

출력

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

예제 입력 1 복사

7
0 1 2 0 1 2 0

예제 출력 1 복사

7

 

알고리즘 분류

• 구현
• 그리디 알고리즘

 

코드

// 메모리: 14308 KB
// 시간 : 132 MS

package 우유축제;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

/*
    [시간 복잡도]

    결론 : O(N) 우유 가게의 수
    N만큼 한 번 순회하며 각 가게의 정보를 확인하고,
    조건에 맞는 우유를 마시기 때문에 시간 복잡도는 O(N)입니다.

    [접근 방법]

    1. 우유 마시는 규칙 정의
    - 딸기우유(0), 초코우유(1), 바나나우유(2)의 순서로 마셔야 하기 때문에, 이를 milkSequence 배열에 정의합니다.
    - milkTypeIndex 변수를 통해 현재 마셔야 하는 우유의 타입을 추적합니다. 초기값은 0 (딸기우유)로 설정합니다

    2. 우유 가게 순회
    - 모든 우유 가게를 순회하면서 현재 가게의 우유 타입이 milkSequence[milkTypeIndex]와 일치하는지 확인합니다.
    - 일치하면 우유를 마시고, 마신 우유 개수(count)를 증가시킵니다.
    - 다음 마셔야 할 우유 타입으로 milkTypeIndex를 업데이트 합니다. 이때, milkTypeIndex는 0, 1, 2를 순환하도록 모듈로 연산(% 3)을 사용합니다.

 */
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine()); // 우유 가게의 수 N 입력

        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] milkStores = new int[N]; // 버퍼에서 우유 가게 정보 입력 받습니다.

        for (int i = 0; i < N; i++) {
            milkStores[i] = Integer.parseInt(st.nextToken());
        }

        // 우유의 종류 (0: 딸기, 1: 초코, 2: 바나나)
/*
        currentMilk를 0으로 초기화한 이유
        문제 설명 참고 시, `딸기 마시고 -> 초코 마시고 -> 바나나 마시고 -> 딸기 마시는` 규칙이 있다고 명시함.
*/
        int[] milkSequence = {0, 1, 2};
        int milkTypeIndex = 0;
        int count = 0;

        // 우유 가게들을 순회하며 영학이가 마실 수 있는 우유의 최대 개수를 계산
        for (int i = 0; i < N; i++) {
            if (milkStores[i] == milkSequence[milkTypeIndex]) {
                count++;

                int nextMilk = milkTypeIndex + 1; // 다음 밀크 타입 시퀀스를 지정함.
                milkTypeIndex = nextMilk % 3; // Ensure the sequence cycles between 0, 1, and 2
            }
        }

        // 결과 출력
        System.out.println(count);

        br.close();
    }
}