글 읽기 - 반레를 좀 부탁드립니다. ㅠ

gyjinro 3년 전 0

DP로 풀어야 되는 문제들은 멍청해서 그런지 도저히 점화식이 안 세워지더라구요.

그래서 무식하게 모든 경우를 고려해서 구현 방식으로 풀어 보려고 노력했습니다만, 역시나 틀렸습니다를 받았습니다. ㅠ

고려한 사항은 아래와 같습니다.

al = 상단 스티커 점수

bl = 하단 스티커 점수

cl = 최대값 저장

d = 현재 인덱스

e = d-1의 선택 상태

0 : [d-2]는 아래 선택, [d-1]은 위 선택

1 : [d-2]는 위 선택, [d-1]은 아래 선택

2 : [d-2] 선택하지 않음, [d-1]은 위 선택

3 : [d-2] 선택하지 않음, [d-1]은 아래 선택

f = 최대값만 선택하면 되는 상태

1) 시작하고 2회

2) 합산 값 비교 중 최대값이 같아 다음 칸에서 어떤 값이든 선택할 수 있는 경우

요렇게 넣고 d를 1부터 n까지 증가 시키면서 cl을 채워 나갔습니다.

그리고 cl이 다 채워지면 마지막 값을 출력하는 방식으로 진행했습니다.

TC나 반례로 올려주신 다른 게시물의 건들은 무사히 통과가 됐으나, 채점에서는 시작하자 마자 "틀렸습니다" 를 받아서서 어느 부분이 잘 못 됐는지 문의 드리고자 질문을 올립니다. ㅠ

그리고 이런 삽질을 방지하기 위해 DP(점화식을 세우는 방법)를 배울 수 있는 좋은 방법이 있을까요?

ㅠㅠ

import sys


def main():
    t = int(input())
    for _ in range(t):
        n = int(sys.stdin.readline())
        al = [0] + list(map(int, sys.stdin.readline().split()))
        bl = [0] + list(map(int, sys.stdin.readline().split()))
        cl = [0] * (n + 1)
        d = 1  # pointer
        e = 0  # state
        f = 2  # re_start
        while d <= n:
            if f == 2:
                a = al[d]
                b = bl[d]
                if a > b:
                    cl[d] = cl[d-1] + a
                    e = 0
                    f -= 1
                elif a < b:
                    cl[d] = cl[d-1] + b
                    e = 1
                    f -= 1
                else:
                    cl[d] = cl[d-1] + a
            elif f == 1:
                a = al[d] + bl[d-1]
                b = al[d-1] + bl[d]
                if a > b:
                    cl[d] = cl[d-2] + a
                    e = 0
                    f -= 1
                elif a < b:
                    cl[d] = cl[d-2] + b
                    e = 1
                    f -= 1
                else:
                    cl[d] = cl[d-2] + a
                    f = 2
            else:
                if e == 0:
                    a = al[d-1] + bl[d]
                    b = al[d]
                    if a > b:
                        cl[d] = cl[d-1] + bl[d]
                        e = 1
                    elif a < b:
                        cl[d] = cl[d-2] + b
                        e = 2
                    else:
                        cl[d] = cl[d-1] + b
                        f = 2
                elif e == 1:
                    a = bl[d-1] + al[d]
                    b = bl[d]
                    if a > b:
                        cl[d] = cl[d-1] + al[d]
                        e = 0
                    elif a < b:
                        cl[d] = cl[d-2] + b
                        e = 3
                    else:
                        cl[d] = cl[d-1] + b
                        f = 2
                elif e == 2:
                    a = al[d-1] + bl[d]
                    b = al[d-2] + bl[d-1] + al[d]
                    if a > b:
                        cl[d] = cl[d-1] + bl[d]
                        e = 1
                    elif a < b:
                        cl[d] = cl[d-2] + bl[d-1] + al[d]
                        e = 0
                    else:
                        cl[d] = cl[d-1] + bl[d]
                        f = 2
                elif e == 3:
                    a = bl[d-1] + al[d]
                    b = bl[d-2] + al[d-1] + bl[d]
                    if a > b:
                        cl[d] = cl[d-1] + al[d]
                        e = 0
                    elif a < b:
                        cl[d] = cl[d-2] + al[d-1] + bl[d]
                        e = 1
                    else:
                        cl[d] = cl[d-1] + al[d]
                        f = 2
            d += 1
        print(cl[d-1])


if __name__ == "__main__":
    main()

djs100201 3년 전 1

dp에 약간 오개념을 고쳐드리자면(이미 알고 계실수도 있지만)

점화식을 세워야만 dp가 아닙니다.
이전 정보를 활용해서 문제를 해결한다는 것이 핵심 개념입니다.
글쓴이님의 접근 방식이 대략 비슷한거 같아서 곧 해결하실거 같구요. 아래는 접근방식을 설명해드리겠습니다.

배열 dp[n+1][2]라는 2차원 배열을 만듭시다.

dp[x][0]을 x번째 까지 왔을때 위쪽 스티커를 반드시 먹을때 점수최댓값.
dp[x][1]을 x번째 까지 왔을때 아래쪽 스티커를 반드시 먹을때 점수최댓값.

으로 정의를 하고 문제를 푸는 겁니다. 그럼 이제 dp값들을 채워나가면서, 이전에 채운 dp값들을 활용할 수 있죠.
모든 값들이 양수인 것도 식을 세워나갈때 고려해야 할 사항입니다.
전형적인 쉬운 dp문제들은 보통 이러한 식으로 x번째까지왔을때 문제의 정답 으로 놓고 하면 해결할 수 있는 경우가 많습니다.

https://www.acmicpc.net/proble...
https://www.acmicpc.net/proble...
등등 쉬운dp는 많이 풀다보면 됩니다. 화이팅

gyjinro 3년 전 0

감사합니다.

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

문제

문제

출처

ICPC

반레를 좀 부탁드립니다. ㅠ

gyjinro 3년 전 0

djs100201 3년 전 1

gyjinro 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말