๋ฌธ์ ๋งํฌ
์ฝ๋ฉํ ์คํธ ์ฐ์ต - ๋ ๋ฐ๋จน๊ธฐ
๋ ๋ฐ๋จน๊ธฐ ๊ฒ์์ ํ๋ ค๊ณ ํฉ๋๋ค. ๋ ๋ฐ๋จน๊ธฐ ๊ฒ์์ ๋ (land)์ ์ด Nํ 4์ด๋ก ์ด๋ฃจ์ด์ ธ ์๊ณ , ๋ชจ๋ ์นธ์๋ ์ ์๊ฐ ์ฐ์ฌ ์์ต๋๋ค. 1ํ๋ถํฐ ๋ ์ ๋ฐ์ผ๋ฉฐ ํ ํ์ฉ ๋ด๋ ค์ฌ ๋, ๊ฐ ํ์ 4์นธ ์ค ํ ์นธ๋ง ๋ฐ
programmers.co.kr
Nํ 4์ด๋ก ์ด๋ฃจ์ด์ง ๋ฐฐ์ด์ด ์ฃผ์ด์ง๊ณ ๊ฐ ์์๋ง๋ค ์ ์๊ฐ ์ฃผ์ด์ง ๋
ํ๋ง๋ค ํ๋์ ๊ฐ์ฉ ๋ํด ๊ฐ์ฅ ํฐ ๊ฐ์ ์ถ๋ ฅํ๋ ๋ฌธ์ ์ด๋ค.
์กฐ๊ฑด : ์ฐ์๋ ์ด๋ก ์ด๋ํ ์ ์๋ค.
์ ๊ทผ ๋ฐฉ๋ฒ
์ด์ ํ์ ๊ฐ์ฅ ํฐ ๊ฐ๊ณผ ํ์ฌ ํ์ ๋ํ๊ณ , ํ์ฌํ์ ๊ฐ์ฅ ํฐ๊ฐ๊ณผ ๋ค์ํ์ ๋ํ๋ฉด์ dp๋ฐฉ์์ผ๋ก ์ ๊ทผํ์๋ค.
1 2 3 4 1 2 3 4
5 6 7 8 => 9 10 11 11
์ฝ๋์ ํต์ฌ์ ์ฐ์๋ ์ด์ ๊ฐ์ ๋ ํ ์ ์์ผ๋ฏ๋ก
land[row][col] += Math.max(...land[row-1].slice(0, col), ...land[row-1].slice(col+1))โ
์ด์ ํ์ ์ด๊ณผ ๊ฐ์ ์ด์ ์ ์ธํ ๋ถ๋ถ์์ Max๊ฐ์ ์ฐพ๋ ๊ฒ์ด๋ค.
function solution(land) {
var answer = 0;
for(let row = 1; row < land.length; row++){
for(let col = 0; col < land[0].length; col++){
land[row][col] += Math.max(...land[row-1].slice(0, col), ...land[row-1].slice(col+1))
}
}
answer = Math.max(...land[land.length-1])
return answer;
}
'์ฝ๋ฉํ ์คํธ > ํ๋ก๊ทธ๋๋จธ์ค' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[Javascript] 1์ฐจ ๋ด์ค ํด๋ฌ์คํธ๋ง (17677) (0) | 2022.06.23 |
---|---|
[Javascript] k์ง์์์ ์์ ๊ฐ์ ๊ตฌํ๊ธฐ (92335) (0) | 2022.06.23 |
[Javascript] ํผ๋ก๋ (87946) (0) | 2022.06.23 |
[Javascript] 2 * n ํ์ผ๋ง (12900) (0) | 2022.06.22 |
[Javascript] ๊ฐ์ฅ ํฐ ์ ์ฌ๊ฐํ (12905) (0) | 2022.06.22 |