sksdong1   1년 전

dp로 각 번호에 대해 카드들이 빠질 조건, 점수를 얻을 조건에 맞춰서 아래와 같이 짯는데 어디가 잘못된걸까요ㅜㅜ

yukariko   1년 전

왼쪽 카드만 버리거나, 오른쪽 카드만 버리거나, 둘 다 버리거나의 3택이 가능한데,

위 소스는 2가지만을 고려한 것 같습니다.

sksdong1   1년 전

23줄에 num=j를 넣고 19줄에서 num부터 탐색 시작하도록 해서 왼쪽만 버리는 용도(num개 만큼) 의도했고

17줄 for문 한바퀴 돌때마다 오른쪽을 버리도록 의도했고, 이 과정에서 점수를 먹는다면 오른쪽만 하나 증가되고, 점수를 못먹는다면

31줄에서 num++ 해서 왼쪽 오른쪽 둘다 버리도록 의도했는데

3개 다 고려한거 아닌가용??

yukariko   1년 전

음.. 이 소스는 동적계획법으로 구현이 된것이 아닌것 같습니다.

지금의 소스는 이전 dp 값을 활용하여 크기 비교하는 과정이 없고,

dp[i][j]에 값을 할당하는 부분만이 존재합니다.

그렇다면 이 소스는 동적계획법이 아닌, 그리디 해법입니다.

오른쪽 카드만 택할 수 있는 상황엔 오른쪽 카드만 택하는게 맞지만,

그 외의 상황에선 왼쪽 카드만 택하거나, 양쪽 카드를 택했을 때의 결과 중의 최대를 골라야 합니다.

sksdong1   1년 전

아 그러네요 감사합니다!!

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