[programmers] 2 x n ํ์ผ๋ง - Java
๊ฐ๋ก ๊ธธ์ด๊ฐ 2์ด๊ณ ์ธ๋ก ๊ธธ์ด๊ฐ n์ธ ์ง์ฌ๊ฐํ์ 2 x 1 ํ์ผ๋ก ์ฑ์ฐ๋ ๋ฐฉ๋ฒ์ ๊ตฌํ๋ ๋ฌธ์ ๋ก, ํ์ผ์ ๊ฐ๋ก ๋๋ ์ธ๋ก๋ก ๋ฐฐ์นํ ์ ์์ต๋๋ค. ์ฃผ์ด์ง n์ ๋ํด ๊ฒฝ์ฐ์ ์๋ฅผ ๊ตฌํ๋ solution ํจ์๋ฅผ ์์ฑํ๋ฉฐ, ๊ฒฐ๊ณผ๋ 1,000,000,007๋ก ๋๋ ๋๋จธ์ง๋ฅผ ๋ฐํํด์ผ ํฉ๋๋ค. ๋์ ํ๋ก๊ทธ๋๋ฐ์ ์ฌ์ฉํ์ฌ dp ๋ฐฐ์ด์ ํตํด ํด๊ฒฐํฉ๋๋ค.
Nov 08, 2024
2 x n ํ์ผ๋ง
๋ฌธ์ ์ค๋ช
๊ฐ๋ก ๊ธธ์ด๊ฐ 2์ด๊ณ ์ธ๋ก์ ๊ธธ์ด๊ฐ 1์ธ ์ง์ฌ๊ฐํ๋ชจ์์ ํ์ผ์ด ์์ต๋๋ค. ์ด ์ง์ฌ๊ฐํ ํ์ผ์ ์ด์ฉํ์ฌ ์ธ๋ก์ ๊ธธ์ด๊ฐ 2์ด๊ณ ๊ฐ๋ก์ ๊ธธ์ด๊ฐ n์ธ ๋ฐ๋ฅ์ ๊ฐ๋ ์ฑ์ฐ๋ ค๊ณ ํฉ๋๋ค. ํ์ผ์ ์ฑ์ธ ๋๋ ๋ค์๊ณผ ๊ฐ์ด 2๊ฐ์ง ๋ฐฉ๋ฒ์ด ์์ต๋๋ค.
- ํ์ผ์ ๊ฐ๋ก๋ก ๋ฐฐ์น ํ๋ ๊ฒฝ์ฐ
- ํ์ผ์ ์ธ๋ก๋ก ๋ฐฐ์น ํ๋ ๊ฒฝ์ฐ
์๋ฅผ๋ค์ด์ n์ด 7์ธ ์ง์ฌ๊ฐํ์ ๋ค์๊ณผ ๊ฐ์ด ์ฑ์ธ ์ ์์ต๋๋ค.
์ง์ฌ๊ฐํ์ ๊ฐ๋ก์ ๊ธธ์ด n์ด ๋งค๊ฐ๋ณ์๋ก ์ฃผ์ด์ง ๋, ์ด ์ง์ฌ๊ฐํ์ ์ฑ์ฐ๋ ๋ฐฉ๋ฒ์ ์๋ฅผ return ํ๋ solution ํจ์๋ฅผ ์์ฑํด์ฃผ์ธ์.
์ ํ์ฌํญ
- ๊ฐ๋ก์ ๊ธธ์ด n์ 60,000์ดํ์ ์์ฐ์ ์ ๋๋ค.
- ๊ฒฝ์ฐ์ ์๊ฐ ๋ง์ ์ง ์ ์์ผ๋ฏ๋ก, ๊ฒฝ์ฐ์ ์๋ฅผ 1,000,000,007์ผ๋ก ๋๋ ๋๋จธ์ง๋ฅผ returnํด์ฃผ์ธ์.
์ ์ถ๋ ฅ ์
n | result |
4 | 5 |
์ ์ถ๋ ฅ ์ ์ค๋ช
์
์ถ๋ ฅ ์ #1
๋ค์๊ณผ ๊ฐ์ด 5๊ฐ์ง ๋ฐฉ๋ฒ์ด ์๋ค.
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