우규이인우윀
Eager To Learn 🌌
우규이인우윀
전체 방문자
였늘
μ–΄μ œ

λΈ”λ‘œκ·Έ 메뉴

  • 🏑 ν™ˆ
  • πŸš€ κΉƒν—ˆλΈŒ
  • β›… νƒœκ·Έ ν΄λΌμš°λ“œ
  • λΆ„λ₯˜ 전체보기 (217)
    • πŸ‘¨πŸ»‍πŸ’» PS (170)
      • JAVA (82)
      • MYSQL (1)
      • Docker (2)
      • PYTHON (24)
      • LeetCode 150 (39)
      • Algorithm 기법 (1)
      • 바킹독 (21)
    • λΈ”λ‘œκ·Έ 이사 (0)
    • Error (1)
    • CS (15)
      • DataBase (2)
      • OS (7)
      • Network (1)
      • Spring (1)
      • 자료ꡬ쑰 (3)
      • Java (1)
    • Learned (7)
      • Spring (7)
    • κ°œλ°œμ„œμ  (15)
      • 가상 λ©΄μ ‘ μ‚¬λ‘€λ‘œ λ°°μš°λŠ” λŒ€κ·œλͺ¨ μ‹œμŠ€ν…œ 섀계 기초 (1)
      • 였브젝트 - 쑰영호 (7)
      • μΉœμ ˆν•œ SQL νŠœλ‹ (7)
    • 회고 (2)
hELLO Β· Designed By μ •μƒμš°.
우규이인우윀

Eager To Learn 🌌

πŸ‘¨πŸ»‍πŸ’» PS/JAVA

[JAVA] λ°±μ€€ 11057번 γ€μ˜€λ₯΄λ§‰ μˆ˜γ€‘

2022. 9. 6. 17:05


νŒ¨ν„΄μ„ μ°ΎκΈ° μœ„ν•΄ 경우의 수λ₯Ό μ‚΄νŽ΄λ³΄μž.

 

0으둜 μ‹œμž‘ν•˜λŠ” 것도 ν—ˆμš©ν•˜κ³ , 00 μ΄λ‚˜ 11 κ³Ό 같이 같은 μˆ«μžκ°€ μ—°μ†λœ κ²½μš°μ—λ„ μ˜€λ¦„μ°¨μˆœμœΌλ‘œ κ°„μ£Όν•˜λ―€λ‘œ

 

μœ„μ™€ 같은 경우의 μˆ˜κ°€ μžˆμ„ 수 μžˆλ‹€.

 

μ΄λ ‡κ²Œ 색을 μΉ ν•˜λ©΄ νŒ¨ν„΄μ΄ 보일 것이닀.

 

즉 N자리 i둜 μ‹œμž‘ν•˜λŠ” 였λ₯΄λ§‰ μˆ˜λŠ” N-1자리 i둜 μ‹œμž‘ν•˜λŠ” 였λ₯΄λ§‰μˆ˜λΆ€ν„° N-1자리 9둜 μ‹œμž‘ν•˜λŠ” 였λ₯΄λ§‰μˆ˜λ₯Ό λ”ν•˜λ©΄ λœλ‹€.

 

Dp[i][j] = Dp[i-1][j] + ····· Dp[i-1][9] 

 

 

μœ„ 식을 ν‘œν˜„ν•˜λ©΄ λ˜λŠ”λ°, λ‚˜λŠ” for문을 3개 μ‚¬μš©ν•˜μ—¬ ν‘œν˜„ν•˜μ˜€λ‹€.

 

for (int i = 2; i <= N; i++) {
			for (int j = 0; j <= 9; j++) {
				for(int k=j;k<=9;k++) {
					Dp[i][j]+=Dp[i-1][k]%mod;
				}
			}
		}

 

iκ°€ 2μΌλ•Œλ₯Ό μ‚΄νŽ΄λ³΄λ©΄,

 

j=0일 λ•Œ,

kλŠ” 0λΆ€ν„° 9κΉŒμ§€ μ§„ν–‰ν•œλ‹€.

즉, Dp[2][0] = Dp[1][0]+ Dp[1][1] +····· + Dp[1][9] κ°€ λœλ‹€.

 

j=1 일 λ•Œ,

kλŠ” 1λΆ€ν„° 9κΉŒμ§€ μ§„ν–‰ν•˜λ―€λ‘œ,

즉, Dp[2][1] = Dp[1][1] + ····· + Dp[1][9] κ°€ λœλ‹€.


κ²°κ³ΌλŠ” μ•„λž˜μ™€ κ°™λ‹€.

 

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int N = scanner.nextInt();
		int [][] Dp = new int[N+1][10];
		int mod = 10007;
		for(int i=0;i<=9;i++) {
			Dp[1][i]=1;
		}
		
		for (int i = 2; i <= N; i++) {
			for (int j = 0; j <= 9; j++) {
				for(int k=j;k<=9;k++) {
					Dp[i][j]+=Dp[i-1][k]%mod; // 였λ₯΄λ§‰ 수 경우의 수 κ΅¬ν•˜λŠ” 식
				}
			}
		}
		
		int sum=0;
		for(int i=0;i<=9;i++) {
			sum+=Dp[N][i]; 
			sum%=mod;
		}
		System.out.println(sum);
	}
}
    'πŸ‘¨πŸ»‍πŸ’» PS/JAVA' μΉ΄ν…Œκ³ λ¦¬μ˜ λ‹€λ₯Έ κΈ€
    • [JAVA] λ°±μ€€ 9465번 γ€μŠ€ν‹°μ»€γ€‘
    • [JAVA] λ°±μ€€ 2193번 γ€μ΄μΉœμˆ˜γ€‘
    • [JAVA] λ°±μ€€ 10844번 γ€μ‰¬μš΄ 계단 μˆ˜γ€‘
    • [JAVA] λ°±μ€€ 9095번 【1, 2, 3 λ”ν•˜κΈ°γ€‘
    우규이인우윀
    우규이인우윀
    개발자 κΏˆλ‚˜λ¬΄

    ν‹°μŠ€ν† λ¦¬νˆ΄λ°”