[자바]백준 14720번 우유 축제 [그리디][엄탱]

안녕하세요. 개발자 엄탱입니다.
이 글은 알고리즘을 공부하면서 공부 기록용입니다.
그래서 설명마다 일기용으로 편하게 작성하여 반말 형식으로 작성하려고 합니다.
그리고 보시다가 더 좋은 방법이나 잘 못 알고 있는 내용이 있다면 알려주시면 정말 감사하겠습니다.
좋은 하루 되세요 :)

 

그리디 알고리즘이란!?

Greedy는 ‘탐욕스러운, 욕심 많은’ 이란 뜻이다.
탐욕 알고리즘은 말 그대로 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법이다.

 

문제

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

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

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

 

알고리즘 분류

• 구현
• 그리디 알고리즘

 

문제 설명

문제는 간단하다 영학이는

1. 딸기우유 (데이터로 0번)
2. 초코우유 (데이터로 1번)
3. 바나나우유 (데이터로 2번)

위의 순서대로만 우유를 마신다.
왜 그런걸까 맛이 약한거 부터 먹으면 좋을 텐데!

 

우유거리가 일직선상에 놓여져 있는데 뒤로 돌아갈 수 없는 상태에서 위와 같은 규칙을 적용 시켰을때 몇개의 우유를 먹을 수 있냐는 문제이다.

 

해설

그리디 알고리즘 특성상 당장에 눈앞의 상황을 고려해 해답에 도달 하는 것이다.

그래서 이 문제는 간단하게 풀 수 있다.

• 딸기 우유(0번)가 나오기전까지는 초코우유(1번), 바나나 우유(2번)은 무시하고 패스
• 딸기 우유를 먹었으면 다음은 초코우유(1번)가 나오기 전까지 딸기우유(1번), 바나나 우유(2번)은 무시하고 패스
• 바나나 우유도 마찬가지로 위와 같이 반복
• 계속 반복해서 카운트 해주면 끝
  
  

import java.io.BufferedWriter;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int T = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int[] arr = new int[T];
        
        for (int i = 0; i < T; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        
        int cnt = 0;
        int cur = 0;
        
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == cur) {
                cnt++;
                cur = (cur + 1) % 3;
            }
        }
        
        bw.write(cnt + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
}