[백준 / BOJ] 14720 우유 축제

문제

출처

www.acmicpc.net/problem/14720

14720번: 우유 축제

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

영학이는 가게를 지나가면서 우유를 먹을건데, 무조건 딸기우유 초코우유 바나나우유 순서로 먹어야한다.

(초코우유를 먹지않고, 딸기우유만 먹었다면 바나나 우유를 먹지못한다.)

이때, 영학이가 먹을수있는 우유의 최대 갯수를 구하는문제다.

 

풀이

딸기우유 : 0, 초코유우 : 1, 바나나우유 : 2 라 할때 영학이가 우유를 먹기 시작할수있는 위치는 0이다.(딸기우유를 파는 가게)

딸기우유를 파는 가게의 idx를 deq에 전부 넣어주고 deq이 비어있을때까지 영학이에게 우유를 먹게 시켰다.

 

이때, N이 최대 1000이고, 현재 우유를 먹지않고 뒤에서 우유를 먹을때 최댓값이 나올수도 있기때문에, 완전탐색으로 풀경우, 2^1000번 봐줄것이라고 생각했다.

 

dp를 섞어서 시간초과를 해결해줬는데,

dp[우유종류][idx] = 최댓값, 으로 저장해서,

현재 idx까지 왔을때 먹을 우유의 종류와 먹은 우유갯수의 최댓값이 dp에 저장된값 보다 작다면 더이상 탐색하지 않고 종료해줬다.

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/14720%20%EC%9A%B0%EC%9C%A0%20%EC%B6%95%EC%A0%9C/main.cpp

devxb/JJUNalgo