글 읽기 - 1149번 거의 다 풀었는데 ㅠㅠ 도와주실 분 계신가요 🥺

guesswhoguessjy 2년 전 0

DP 이용해서

26 40 83

49 60 57

13 89 99

라면

( i = 0 )

min(49,60,57) = 49

57 !=49 이므로 49 부터 타고 올라오면 값이 더 작아질지 비교

26-> 57 vs 40 ->49

=> 26 -> 57

( i = 1 )

min(13,89,99) = 13

26 부터 타고 내려갔을 때랑 13 동일하므로 continue

26 -> 57 -> 13

이런 식으로 값을 구했는데

10
84 78 43
25 24 56
24 22 63
24 61 34
64 68 32
12 42 33
25 64 53
74 92 63
74 61 54
34 68 32

결과 : 369

여기서 막혔습니다.

[43, 25,22 24, 32, 12, 53, 74, 54, 34] -> 373 이 나와버려요 ㅠㅠ

접근 방식에서 무엇을 변경해야할지 질문드립니다 !

중간 중간 제가 값을 찍어보려고 사이 과정도 같이 print 해보았습니다.

최종 답은 print(summ) 입니다

import sys
import copy
input=sys.stdin.readline

class RGB:
    def read(self):
        self.hn=int(input())
        self.info=[list(map(int,input().split())) for _ in range(self.hn)]
    
    def solve(self):
        info=copy.deepcopy(self.info)
        p1=min(info[0])
        summ=p1
        if info[0].count(p1)==1:
            c1=info[0].index(p1)
            info[1][c1]=float("inf")
        r1=[p1]
        for i in range(1,self.hn):
            print(i,end=' i\n')
            p1=min(info[i])
            c1=info[i].index(p1)
            if i<self.hn-1:
                info[i+1][c1]=float("inf")
            summ+=p1
            r1.append(p1)
            info2=copy.deepcopy(self.info)
            r=i
            summ2=0
            p2=min(info2[i])
            if p2==r1[-1]:
                continue
            summ2+=p2
            r2=[p2]
            r-=1
            if info2[i].count(p2)==1:
                c2=info2[i].index(p2)
                info2[i-1][c2]=float("inf")
            while r>=0:
                print(r, end=' r\n')
                p2=min(info2[r])
                if info2[r].count(p2)==1:
                    c2=info2[r].index(p2)
                    if r>0:
                        info2[r-1][c2]=float("inf")
                summ2+=p2 
                r-=1
                r2.append(p2)
                print(r2,end= ' temp\n')
            print(r1,end= ' r1\n')
            print(r2,end=' r2\n')
            print(summ)
            print(summ2)
            if summ>summ2:
                r1=r2
                summ=summ2 
                info=info2
                c1=info[i].index(r1[0])
                if i<self.hn-1:
                    info[i+1][c1]=float("inf")
        print(summ)     
rgb=RGB()
rgb.read()        
rgb.solve()

terrryahn78 2년 전 1

이 코드는 DP 가 아니라 DFS에 가깝습니다.

위 코드의 반례로

123

112

212

가 있습니다.

모든 경우를 따지기 위해서는 합을 누적하는 알고리즘이 필요합니다.

코드를 아래에 첨부하겠습니다.

nx = {0:[1,2], 1:[0,2], 2:[0,1]}

hold = [0,0,0]

N = int(input())
for i in range(N):
  cost = [int(x) for x in input().split()]
  for j in range(3):
    cost[j]+=min(hold[nx[j][0]], hold[nx[j][1]])
  hold = cost

print(min(cost))

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

문제

문제

출처

ICPC

1149번 거의 다 풀었는데 ㅠㅠ 도와주실 분 계신가요 🥺

guesswhoguessjy 2년 전 0

terrryahn78 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말