글 읽기 - 14722 우유도시 / 간단한 dp문제인데 어디가 틀렸을까요

Green55 6년 전 0

1차원 배열이 주어지는 14720 우유축제(https://www.acmicpc.net/proble...)은 거의 같은 알고리즘으로 풀었는데

이 문제는 예제도 제대로 안 돌아가네요..

@cheetose 당연한걸 간과하고 있었네요 감사합니다!
(댓글이 먹통이라 글 수정으로 남깁니다)

#include<bits/stdc++.h>
using namespace std;
int n, milk[1000][1000], dp[1000][1000];
inline int next(int i){
	return i==2 ? 0 : i+1;
}
//현재 what의 우유를 마실 차례일 때, (x,y)에서부터 먹을 수 있는 우유의 개수  
int drink(int what, int x, int y){ 
	if(x==n || y==n) return 0;
	int& ret = dp[x][y];
	if(ret==-1){
		if(milk[x][y] == what) ret = max({
			drink(what, x+1, y),
			drink(what, x, y+1),
			1+drink(next(what), x+1, y),
			1+drink(next(what), x, y+1)
		});
		else ret = max(drink(what, x+1, y), drink(what, x, y+1));
	}
	return ret;
}
int main(){
	scanf("%d", &n);
	for(int i=0; i<n; i++) 
		for(int j=0; j<n; j++)
			scanf("%d", &milk[i][j]);
	memset(dp,-1,sizeof(dp));
	printf("%d", drink(0,0,0));
}

cheetose 6년 전 0

dp 테이블에 what에 해당하는 공간도 만들고 다시 풀어보세요!

dp[3][1000][1000] 이렇게요!

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

문제

문제

출처

ICPC

14722 우유도시 / 간단한 dp문제인데 어디가 틀렸을까요

Green55 6년 전 0

cheetose 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말