글 읽기 - 맞긴 맞았는데 이해가 안 가는 부분이 있습니다.

tajava2006 2년 전 0

22번 째 줄 말인데요, 처음에는

dp[i] = dp[j]+arr[i] 라고 해놨다고 틀렸거든요.

근데 22번째 줄은 21번째 if문을 통과해야 실행되는 것이고 그 if문을 통과한다는 시점에서

dp[j]+arr[i] 가 기존에 15번째 줄에서 초기화로 넣어줬던 arr[i]보다는 무조건 더 큰 거 아닌가요?

혹시 뭐 음수가 들어올 수 있어서 그런가 해서 문제를 봤는데 다 양수고요

왜 max를 해서 둘 중에 더 큰 값을 선택해줘야 하는 걸까요 아무리 생각해도 dp[j]+arr[i]가 arr[i]보다 더 큰 게 백퍼센트 확실한 거 같은데

from functools import reduce
import sys
from copy import deepcopy
sys.setrecursionlimit(1000000)
from collections import defaultdict, deque
read = sys.stdin.readline
write = sys.stdout.write
from heapq import *
from pprint import pprint
from math import *


n = int(read())

arr = list(map(int,read().split()))

dp = [arr[i] for i in range(n)]

for i in range(n):
    for j in range(i):
        if arr[i] > arr[j]:
            dp[i] = max(dp[i],dp[j]+arr[i])

print(max(dp))

gurugeonu 2년 전 1

arr[i]와 dp[j]+arr[i]의 최대가 아니라 dp[i]와 dp[j]+arr[i]의 최대입니다

tajava2006 2년 전 0

...아!

감사합니다.

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

문제

문제

출처

ICPC

맞긴 맞았는데 이해가 안 가는 부분이 있습니다.

tajava2006 2년 전 0

gurugeonu 2년 전 1

tajava2006 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말