우유 축제
1 초 | 256 MB | 7609 | 4512 | 4003 | 61.115% |
문제
영학이는 딸기우유, 초코우유, 바나나우유를 좋아한다.
입맛이 매우 까다로운 영학이는 자신만의 우유를 마시는 규칙이 있다.
- 맨 처음에는 딸기우유를 한 팩 마신다.
- 딸기우유를 한 팩 마신 후에는 초코우유를 한 팩 마신다.
- 초코우유를 한 팩 마신 후에는 바나나우유를 한 팩 마신다.
- 바나나우유를 한 팩 마신 후에는 딸기우유를 한 팩 마신다.
영학이는 우유 축제가 열리고 있는 우유거리에 왔다. 우유 거리에는 우유 가게들이 일렬로 늘어서 있다.
영학이는 우유 거리의 시작부터 끝까지 걸으면서 우유를 사먹고자 한다.
각각의 우유 가게는 딸기, 초코, 바나나 중 한 종류의 우유만을 취급한다.
각각의 우유 가게 앞에서, 영학이는 우유를 사마시거나, 사마시지 않는다.
우유거리에는 사람이 많기 때문에 한 번 지나친 우유 가게에는 다시 갈 수 없다.
영학이가 마실 수 있는 우유의 최대 개수를 구하여라.
입력
첫째 줄에 우유 가게의 수 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();
}
}
'여러가지 > 알고리즘 & 자료구조' 카테고리의 다른 글
[백준] 가장 긴 증가하는 부분 수열 - 11053번 (1) | 2024.06.15 |
---|---|
DP(Dynamic Programming) 핥아보기 (0) | 2024.06.15 |
[백준] 한조서열정리하고옴ㅋㅋ - 14659번 (1) | 2024.06.14 |
[백준] 거스름돈 - 5585번 (1) | 2024.06.14 |
[백준] A->B - 16953번 (0) | 2024.06.14 |