글 읽기 - DP 를 이용한 파스타 문제 질문드립니다.

inspire12 6년 전 0

문제 조건이 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일 연속 먹지 않는다 조건에 걸리지 않으니까요

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

#include <iostream>
#include <stdio.h>

int pick[1003];
long long int pasta[1003][4];
int main(){
  int N,K; scanf("%d%d",&N,&K);
  int a,b;
  for(int i=0; i<K; i++){
    scanf("%d%d",&a,&b);
    pick[a] = b;
  }
  for(int i=1; i<=3; i++){
    pasta[1][i] = 1;
    if(pick[1] > 0) {
      for(int j=1; j<=3; j++){
        if(j==pick[1]) continue;
        pasta[1][j] = 0;
      }
    }
  }
  for(int i=2; i<=N; i++){
    for(int j=1; j<=3; j++){
      for(int k=1; k<=3; k++){
        pasta[i][j] += pasta[i-1][k];
      }
      if(pasta[i][j] > 10000)pasta[i][j]%=10000;
      if(pasta[i-1][j] != 0) pasta[i][j] -= pasta[i-2][j];

      if(pasta[i][j]<0) pasta[i][j]+=10000;
    }
    if(pick[i]>0){
      for(int k=1; k<=3; k++){
        if(k==pick[i]) continue;
        pasta[i][k] = 0;
      }
    }
  }
  // // debug
  // for(int k =1; k<=3; k++){
  //   for(int i=1; i<=N;i++){
  //     printf("%lld",pasta[i][k]);
  //   }
  //   printf("\n");
  // }
  long long int sum = 0;
  for(int i=0; i<=3; i++)
    sum += pasta[N][i];
  printf("%lld",sum%10000);
}

lyzqm 6년 전 1

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

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

haya0206 6년 전 0

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

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