[TIL] 24.07.08

내가 푼 문제 📖

내가 작성한 코드 💻

let [buy, ...input] = require("fs")
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : __dirname+"/input.txt")
  .toString()
  .trim()
  .split('\n')

const N = +buy
const cardPacks = input[0].split(' ').map(Number)
const memo = Array.from({length: N + 1}, () => 0)

for(let i=1; i<=N; i++){
  for(let j=1; j<=i; j++){
    memo[i] = Math.max(memo[i], memo[i - j] + cardPacks[j - 1])
  }
}

console.log(memo[N])

 

어려웠던 점 ❓

1. 최댓값 비교하기

for(let i=1; i<=N; i++){
  for(let j=1; j<=i; j++){
    memo[i] = Math.max(memo[i], memo[i - j] + cardPacks[j - 1])
  }
}

 

최댓값 비교하는 부분이 생각해 내기가 정말로 어려웠다. 1시간을 넘게 고민해 봤지만 해결방법이 떠오르질 않아 구글 서치를 통해 도움을 얻었다.

 

회고 🧐

얼른 DP 끝내고 DFS/BFS 알고리즘으로 넘어가고 싶당..ㅜㅜ

---

출처 🏷️

https://www.acmicpc.net/problem/11052