inspire12   4년 전

문제 조건이 RGB 거리랑 유사한 문제입니다. 

요약하면 2일까지는 먹는게 이어서 가능하고 각 날마다 먹을 파스타가 정해져 있는 두가지 조건입니다. 

그래서 경우의 수를 구할 때 파스타가 안 정해 있으면 

토마토 파스타를 먹을 경우

pasta[i+1 ][1] = pasta[i] [1] + pasta[i] [2] + pasta[i] [3]  - pasta[i-1] [ 1]  

pasta[i+1 ][2] = pasta[i] [1] + pasta[i] [2] + pasta[i] [3]  - pasta[i-1] [ 2] 

pasta[i+1 ][3] = pasta[i] [1] + pasta[i] [2] + pasta[i] [3]  - pasta[i-1] [ 3] 

이런식으로 점화식을 짰습니다. 2일 전에 먹은 음식이 겹치면 빼고 

만약 지정되어있다면 다른 건 0으로 초기화합니다. 그럼 다음에 더할 때 고려를 안할테니까요

그리고 0으로 초기화 된 거라면 -pasta[i-1][j] 를 하지 않게 했습니다. 전날 그걸 안 먹었으면 3일 연속 먹지 않는다 조건에 걸리지 않으니까요


코드도 첨부할게요. 반례라도 부탁드립니다 ㅠㅠ


lyzqm   4년 전

저는 점화식을 3차원으로 만들어서 풀었습니다.

dp[day][latest][newest] : day일째 날일때 이틀전에 먹은 음식이 latest, 하루전에 먹은 음식이 newest일때 경우의 수

haya0206   3년 전

윗님 감사합니다!!!!!덕분에 풀었습니다!!!

댓글을 작성하려면 로그인해야 합니다.