Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
Tags
- setTiemOut
- 2667
- 함수 이놈
- 1568
- html5
- 1543
- javascript
- 1236
- 1302
- 동적계획법
- 함수 선언문
- 1904
- baekjoon
- 렉시컬 스코프
- 자류구조
- 11399
- 1668
- 함수 arguments
- 유사배열
- 1931
- 배열같은배열아닌너
- 비동기처리
- 9461
- 호이스팅
- 탐욕 알고리즘
- 11047
- 백준
- 함수 parmater
- Async/Await
- event loop
Archives
- Today
- Total
두치의 개발공부
BaekJoon_1932(정수 삼각형) 본문
문제 풀이
배열을 피라미드 형식으로 그려서 확인 하면 훨씬 보기 편하다.
위에서 아래로 내려오면서 숫자를 더하는 방향보다는, 아래에서 위의 어떤 숫자와 더할 것인지 선택하는 방향으로 생각하면 좀 더 쉽게 접근 할 수 있다.
7 -1
3 8 -2
8 1 0 -3
3번째의 8은 2번째의 3과 더할 수 밖에 없다.
3번째의 0은 2번째의 8과 더할 수 밖에 없다.
3번째의 1은 2번째의 3과 8 중에서 큰 값을 더하면 된다.
이를 점화식으로 나타내면 아래와 같다.
j = 0 일 때, dp[i][j] += dp[i-1][j]
j = 1 일 때, dp[i][j] += dp[i-1][j-1]
나머지의 경우에는 dp[i][j] += Math.max(dp[i-1][j-1], dp[i-1][j])
코드
const answer = ([n, ...arr]) => {
const dp = [];
for (let i = 0; i < Number(n); i++) {
dp.push(arr[i].split(" ").map(Number));
}
for (let i = 1; i < Number(n); i++) {
for (let j = 0; j <= i; j++) {
let temp;
if (j === 0) {
temp = dp[i - 1][j] // 인덱스 0이면 바로 위의 인덱스 0번 숫자와 더하기
}
else if (j === i) {
temp = dp[i - 1][j - 1] // 인덱스가 마지막이면 바로 위의 인덱스 마지막 숫자와 더하기
}
else {
temp = Math.max(dp[i - 1][j - 1], dp[i - 1][j]) // 위의 2개 중 큰 숫자를 더하기
}
dp[i][j] += temp;
}
}
console.log(Math.max(...dp[n - 1]));
};
const input = [];
require("readline")
.createInterface(process.stdin, process.stdout)
.on("line", (line) => {
input.push(line);
})
.on("close", () => {
// console.log(input)
answer(input);
process.exit();
});
코드는 깃헙에서도 확인 가능합니다 :)
https://github.com/duduchi/Algorithm/tree/main/Dynamic
'알고리즘' 카테고리의 다른 글
BaekJoon_11047(동전) (0) | 2022.05.09 |
---|---|
BaekJoon_11399(ATM) (0) | 2022.05.06 |
BaekJoon_1149(RGB 거리) (0) | 2022.05.03 |
BaekJoon_9461 (파도반 수열) (0) | 2022.04.30 |
BaekJoon_1904(01타일) (0) | 2022.04.28 |