@Eeap
velog
@Eeap
전체 방문자
오늘
어제
  • 전체 (168)
    • osam (1)
    • Cloud (21)
      • Docker (2)
      • AWS (13)
    • AI & Data (7)
    • Algorithm (76)
      • Baekjoon (75)
      • Codeforces (1)
    • Language (18)
      • Java (18)
    • Back-end (17)
      • Spring (3)
      • JSP & Servlet (12)
      • Go (2)
    • 일상 (4)
    • 기타 (8)
    • git (1)
    • Infra (9)
      • Apache Kafka (5)
      • Kubernetes (4)
      • 기타 (0)

블로그 메뉴

  • 홈
  • 태그

공지사항

인기 글

태그

  • knowledge bases
  • 오블완
  • 인터페이스
  • invokemodel api
  • sagemaker unified studio
  • bedrock
  • bedrock agent
  • AWS CodeArtifact
  • bedrock api
  • AWS CodeStar
  • 티스토리챌린지
  • SageMaker
  • Python
  • CLASS
  • flink
  • Agent
  • 심폴릭링크
  • java
  • converse api
  • AWS CodeCatalyst

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
@Eeap

velog

Algorithm/Baekjoon

2225번 파이썬

2022. 4. 10. 16:07
반응형

https://www.acmicpc.net/problem/2225

 

2225번: 합분해

첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다.

www.acmicpc.net

이 문제는 규칙을 찾고 dp를 이용해서 푸는 문제이다.

  n=1 n=2 n=3 n=4 n=
k=1 1 1 1 1 1
k=2 2 3 4 5 6
k=3 3 6 10 15 21

n=1일때는 k의 개수에 따라 경우의 수가 달라지고 k가 1일때는 경우의 수가 한개이므로 전부다 한개이다!

따라서 이 두경우는 모두 초기화를 해주어야한다. 또한, k=2일때도 경우의수가 n+1이므로 이 경우도 같이 초기화를 해준다.

그리고 k,n이 2이상부터 p[k][n]이 p[k-1][n]+p[k][n-1]이라는 것을 알 수 있는데 이건 쉽게 예제로 생각해보면 k,n이 3,3인 dp를 구할때 2,3과 3,2를 구하게 되는데

2,3의 경우 개수를 한개 증가시키면(0을 추가시켜주면됨) 3,3이 되고

(2,1),(1,2),(3,0),(0,3) 

3,2의 경우 숫자를 하나만 증가시켜주면 3,3이 된다.

(2,0,0), (0,2,0),(0,0,2),(1,1,0),(0,1,1),(1,0,1)

이 내용을 코드로 작성해보면 다음과 같이 작성할 수 있다!

import sys
input = sys.stdin.readline
n,k=map(int,input().split())
p = [[0 for _ in range(201)] for __ in range(201)]
for i in range(n+1):
  p[1][i]=1
  p[2][i]=i+1
for k_i in range(2,k+1):
  p[k_i][1]=k_i
  for n_i in range(2,n+1):
    p[k_i][n_i]=(p[k_i-1][n_i]+p[k_i][n_i-1])%1000000000

print(p[k][n])
반응형
저작자표시 (새창열림)

'Algorithm > Baekjoon' 카테고리의 다른 글

1520번 파이썬  (0) 2022.04.12
1890번 파이썬  (0) 2022.04.11
16194번 파이썬  (0) 2022.04.09
4948번 파이썬  (0) 2022.04.09
2293번 파이썬  (0) 2022.04.09
    'Algorithm/Baekjoon' 카테고리의 다른 글
    • 1520번 파이썬
    • 1890번 파이썬
    • 16194번 파이썬
    • 4948번 파이썬
    @Eeap
    @Eeap

    티스토리툴바