[programmers] 2 x n ํƒ€์ผ๋ง - Java

๊ฐ€๋กœ ๊ธธ์ด๊ฐ€ 2์ด๊ณ  ์„ธ๋กœ ๊ธธ์ด๊ฐ€ n์ธ ์ง์‚ฌ๊ฐํ˜•์„ 2 x 1 ํƒ€์ผ๋กœ ์ฑ„์šฐ๋Š” ๋ฐฉ๋ฒ•์„ ๊ตฌํ•˜๋Š” ๋ฌธ์ œ๋กœ, ํƒ€์ผ์„ ๊ฐ€๋กœ ๋˜๋Š” ์„ธ๋กœ๋กœ ๋ฐฐ์น˜ํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ์ฃผ์–ด์ง„ n์— ๋Œ€ํ•ด ๊ฒฝ์šฐ์˜ ์ˆ˜๋ฅผ ๊ตฌํ•˜๋Š” solution ํ•จ์ˆ˜๋ฅผ ์ž‘์„ฑํ•˜๋ฉฐ, ๊ฒฐ๊ณผ๋Š” 1,000,000,007๋กœ ๋‚˜๋ˆˆ ๋‚˜๋จธ์ง€๋ฅผ ๋ฐ˜ํ™˜ํ•ด์•ผ ํ•ฉ๋‹ˆ๋‹ค. ๋™์  ํ”„๋กœ๊ทธ๋ž˜๋ฐ์„ ์‚ฌ์šฉํ•˜์—ฌ dp ๋ฐฐ์—ด์„ ํ†ตํ•ด ํ•ด๊ฒฐํ•ฉ๋‹ˆ๋‹ค.
DriedPollack's avatar
Nov 08, 2024
[programmers] 2 x n ํƒ€์ผ๋ง - Java

2 x n ํƒ€์ผ๋ง

๋ฌธ์ œ ์„ค๋ช…

๊ฐ€๋กœ ๊ธธ์ด๊ฐ€ 2์ด๊ณ  ์„ธ๋กœ์˜ ๊ธธ์ด๊ฐ€ 1์ธ ์ง์‚ฌ๊ฐํ˜•๋ชจ์–‘์˜ ํƒ€์ผ์ด ์žˆ์Šต๋‹ˆ๋‹ค. ์ด ์ง์‚ฌ๊ฐํ˜• ํƒ€์ผ์„ ์ด์šฉํ•˜์—ฌ ์„ธ๋กœ์˜ ๊ธธ์ด๊ฐ€ 2์ด๊ณ  ๊ฐ€๋กœ์˜ ๊ธธ์ด๊ฐ€ n์ธ ๋ฐ”๋‹ฅ์„ ๊ฐ€๋“ ์ฑ„์šฐ๋ ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค. ํƒ€์ผ์„ ์ฑ„์šธ ๋•Œ๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™์ด 2๊ฐ€์ง€ ๋ฐฉ๋ฒ•์ด ์žˆ์Šต๋‹ˆ๋‹ค.
  • ํƒ€์ผ์„ ๊ฐ€๋กœ๋กœ ๋ฐฐ์น˜ ํ•˜๋Š” ๊ฒฝ์šฐ
  • ํƒ€์ผ์„ ์„ธ๋กœ๋กœ ๋ฐฐ์น˜ ํ•˜๋Š” ๊ฒฝ์šฐ
์˜ˆ๋ฅผ๋“ค์–ด์„œ n์ด 7์ธ ์ง์‚ฌ๊ฐํ˜•์€ ๋‹ค์Œ๊ณผ ๊ฐ™์ด ์ฑ„์šธ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.
notion image
์ง์‚ฌ๊ฐํ˜•์˜ ๊ฐ€๋กœ์˜ ๊ธธ์ด n์ด ๋งค๊ฐœ๋ณ€์ˆ˜๋กœ ์ฃผ์–ด์งˆ ๋•Œ, ์ด ์ง์‚ฌ๊ฐํ˜•์„ ์ฑ„์šฐ๋Š” ๋ฐฉ๋ฒ•์˜ ์ˆ˜๋ฅผ return ํ•˜๋Š” solution ํ•จ์ˆ˜๋ฅผ ์™„์„ฑํ•ด์ฃผ์„ธ์š”.

์ œํ•œ์‚ฌํ•ญ

  • ๊ฐ€๋กœ์˜ ๊ธธ์ด n์€ 60,000์ดํ•˜์˜ ์ž์—ฐ์ˆ˜ ์ž…๋‹ˆ๋‹ค.
  • ๊ฒฝ์šฐ์˜ ์ˆ˜๊ฐ€ ๋งŽ์•„ ์งˆ ์ˆ˜ ์žˆ์œผ๋ฏ€๋กœ, ๊ฒฝ์šฐ์˜ ์ˆ˜๋ฅผ 1,000,000,007์œผ๋กœ ๋‚˜๋ˆˆ ๋‚˜๋จธ์ง€๋ฅผ returnํ•ด์ฃผ์„ธ์š”.

์ž…์ถœ๋ ฅ ์˜ˆ

n
result
4
5

์ž…์ถœ๋ ฅ ์˜ˆ ์„ค๋ช…

์ž…์ถœ๋ ฅ ์˜ˆ #1
๋‹ค์Œ๊ณผ ๊ฐ™์ด 5๊ฐ€์ง€ ๋ฐฉ๋ฒ•์ด ์žˆ๋‹ค.
notion image
notion image
notion image
notion image
notion image

solution.java

class Solution { public int solution(int n) { // mod ๊ฐ’ int MOD = 1_000_000_007; // n์ด 1 ๋˜๋Š” 2์ผ ๊ฒฝ์šฐ ์˜ˆ์™ธ์ฒ˜๋ฆฌ if (n == 1) return 1; if (n == 2) return 2; // 2 x n ๋ฐ”๋‹ฅ์„ ์ฑ„์šฐ๋Š” ๋ฐฉ๋ฒ•์„ ์ €์žฅํ•˜๋Š” dp ๋ฐฐ์—ด int[] dp = new int[n + 1]; dp[1] = 1; dp[2] = 2; // ๋ฐ˜๋ณต์œผ๋กœ dp ๋ฐฐ์—ด ์ฑ„์šฐ๊ธฐ for (int i = 3; i <= n; i++) { dp[i] = (dp[i - 1] + dp[i - 2]) % MOD; } return dp[n]; } }
 

ํ•ต์‹ฌ ํ‚ค์›Œ๋“œ

  • n-1๊ณผ n-2์˜ ๊ฒฐ๊ณผ๋ฅผ ํ•ฉ์น˜๋ฉด n์ผ๋•Œ์˜ ๊ฐ’์ด ๋‚˜์˜ค๋ฏ€๋กœ, ์ด ๊ฐ’์— MOD๋กœ ๋‚˜๋จธ์ง€ ์—ฐ์‚ฐ์„ ํ•œ ๊ฐ’์„ ๊ตฌํ•˜๋ฉด ์ •๋‹ต์ด ๋œ๋‹ค.
 

๊ฒฐ๋ก !

๊ทœ์น™์„ ํ•œ๋ฒˆ ์ฐพ์•„๋‚ด๋ฉด ์‰ฝ๊ฐœ ํ’€ ์ˆ˜ ์žˆ๋Š” ๋ฌธ์ œ์˜€๋‹ค.
 
Share article

More articles

See more posts

๐Ÿ‘จ๐Ÿปโ€๐Ÿ’ปDriedPollack's Blog