다이나믹프로그래밍2

• 

  [Java] 백준 10844 : 쉬운 계단 수 https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net dp [][]의 이차원 배열을 사용해서 사용하면 된다. dp [N][i]로 N은 몇 개짜리 계단인지를 의미하고, i는 가장 맨 앞의 자릿수가 i일 때를 의미한다. 이 내용을 그림으로 정리해봤다. dp [][]의 값 에는 해당 개수가 들어갈 예정이다. 예를 들어, dp [2][3]= 2 이렇게. 그러면 어떻게 이 값을 구하냐가 문제인데 간단하다. dp [2][3]일 때 만들 수 있는 계단은 3(N+1)과 3(N-1)이다. 즉, 34와 32이다. 하나의 계단이 추가되는 것이니까 dp [1][2]와 dp [1][4].. 코딩테스트/백준 2023. 2. 4.

• [Java] 백준 1932 : 정수 삼각형 https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택해서 더해가야 한다. 배열에는 아래처럼 저장되어 있다. 7 0 0 0 0 3 8 0 0 0 8 1 0 0 0 2 7 4 4 0 4 5 2 6 5 여기서 그래프의 대각선 왼쪽 또는 대각선 오른쪽은 배열에서 자신의 바로 위에 있는 수 혹은 자신의 왼쪽위에 있는 수 이다. 그래서 가장 왼쪽에 있는 수 즉, i=0인 경우 왼쪽 위는 존재 하지 않으므로 if(j==0) { arr[i][j]=arr[.. 코딩테스트/백준 2023. 2. 3.