이 영역을 누르면 첫 페이지로 이동
시간의화살 블로그의 첫 페이지로 이동

시간의화살

페이지 맨 위로 올라가기

시간의화살

행복하세요

[백준] 18427 함께 블록 쌓기 - Java

  • 2022.09.04 16:31
  • Algorithm/Baekjoon

 

 

 

다이나믹 프로그래밍 유형 문제는 dp 배열 디자인과 점화식 설정이 90%, 나머지 10%는 구현이다.

 

키보드를 치는 시간보다 종이에 배열 디자인, 점화식 구하는 시간이 훨씬 더 길다..

 

dp[i][j] : 1 ~ i 번 까지 학생이 높이가 j인 탑을 만드는 경우의 수

 

학생이 블럭을 사용하지 않는경우도 있으니 점화식은 이 부분을 고려해서 작성해야 한다.

 

dp[i][j] = dp[i-1][j] (i 번째 학생이 블럭을 사용하지 않음) + dp[i][j - list[i].get(k)] (i번째 학생이 어떤 블럭을 사용함)

 

 

 

import java.io.*;
import java.util.*;

public class Main {	
	static int INF = 987654321;	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());

		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		int H = Integer.parseInt(st.nextToken());

		ArrayList<Integer>[] list = new ArrayList[N + 1];
		int[][] dp = new int[N + 1][H + 1];

		for(int i=1; i<N+1; i++){
			list[i] = new ArrayList<>();
			st = new StringTokenizer(br.readLine());		

			while(st.hasMoreTokens()){
				list[i].add(Integer.parseInt(st.nextToken()));
			}
		}

		for(int i=0; i<list[1].size(); i++){
			dp[1][list[1].get(i)] = 1;
		}

		for(int i=0; i<N+1; i++){
			dp[i][0] = 1;
		}

		for(int i=2; i<N+1; i++){
			for(int j=1; j<H+1; j++){
				dp[i][j] = dp[i-1][j];
				dp[i][j] %= 10007;
				for(int k=0; k<list[i].size(); k++){
					if(j - list[i].get(k) <= -1){
						continue;
					}
					dp[i][j] += dp[i-1][j-list[i].get(k)];
					dp[i][j] %= 10007;
				}
			}
		}	
	
		System.out.println(dp[N][H]);						
		
	}
}

 

반응형
저작자표시 (새창열림)

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

[백준] 13156 Selling CPUs - Java  (1) 2022.09.14
[백준] 1823 수확 - Java  (0) 2022.09.13
[백준] 2228 구간 나누기 - Java  (0) 2022.09.03
[백준] 20152 Game Addiction - Java  (1) 2022.08.28
[백준] 2876 그래픽스 퀴즈 - Java  (1) 2022.08.28

댓글

이 글 공유하기

  • 구독하기

    구독하기

  • 카카오톡

    카카오톡

  • 라인

    라인

  • 트위터

    트위터

  • Facebook

    Facebook

  • 카카오스토리

    카카오스토리

  • 밴드

    밴드

  • 네이버 블로그

    네이버 블로그

  • Pocket

    Pocket

  • Evernote

    Evernote

다른 글

  • [백준] 13156 Selling CPUs - Java

    [백준] 13156 Selling CPUs - Java

    2022.09.14
  • [백준] 1823 수확 - Java

    [백준] 1823 수확 - Java

    2022.09.13
  • [백준] 2228 구간 나누기 - Java

    [백준] 2228 구간 나누기 - Java

    2022.09.03
  • [백준] 20152 Game Addiction - Java

    [백준] 20152 Game Addiction - Java

    2022.08.28
다른 글 더 둘러보기

정보

시간의화살 블로그의 첫 페이지로 이동

시간의화살

  • 시간의화살의 첫 페이지로 이동

검색

방문자

  • 전체 방문자
  • 오늘
  • 어제

카테고리

  • 분류 전체보기 (605) N
    • Algorithm (205)
      • Data Structure (5)
      • Theory && Tip (33)
      • Baekjoon (166)
      • ALGOSPOT (1)
    • Spring (123)
      • Spring (28)
      • Spring Web MVC (20)
      • Spring Database (14)
      • Spring Boot (6)
      • Spring 3.1 (11)
      • Spring Batch (6)
      • Spring Security (16)
      • JPA (12)
      • Spring Data JPA (5)
      • QueryDSL (4)
      • eGovFramework (1)
    • Programming Language (74)
      • Java (19)
      • JavaScript (15)
      • C (25)
      • C++ (12)
      • Python (1)
      • PHP (2)
    • Computer Science (68) N
      • Operating System (18)
      • Computer Network (16) N
      • System Programming (22)
      • Universial Programming Lang.. (8)
      • Computer Architecture (4)
    • Database (21)
      • Database (7)
      • MySQL (3)
      • Oracle (3)
      • Redis (5)
      • Elasticsearch (3)
    • DevOps (20)
      • Docker && Kubernetes (8)
      • Jenkins (4)
      • Github Actions (0)
      • Amazon Web Service (8)
    • Machine Learning (28)
      • AI Introduction (28)
    • Mobile (28)
      • Android (21)
      • Flutter (7)
    • Solutions (13)
    • Life Logs (0)
    • 낙서장 (25)

최근 글

나의 외부 링크

메뉴

  • 홈

정보

13months의 시간의화살

시간의화살

13months

블로그 구독하기

  • 구독하기
  • RSS 피드

티스토리

  • 티스토리 홈
  • 이 블로그 관리하기
  • 글쓰기
Powered by Tistory / Kakao. Copyright © 13months.

티스토리툴바