카테고리 없음
[BOJ - 18427] 함께 블록 쌓기
먼지의삶
2020. 2. 14. 17:12
https://www.acmicpc.net/problem/18427
18427번: 함께 블록 쌓기
첫째 줄에 자연수 N, M, H가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 50, 1 ≤ M ≤ 10, 1 ≤ H ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 각 학생이 가진 블록들의 높이가 공백을 기준으로 구분되어 주어진다. 단, 모든 블록의 높이는 1,000 이하의 자연수이며 한 명의 학생이 가지고 있는 모든 블록들의 높이는 서로 다르게 주어진다.
www.acmicpc.net
재귀로 여러번했다가 실패했는데,
아마.. 시간 복잡도가 대략 10의 50승이 나오기 때문일것이다.
제일좋은 방법은 Dynamic Programming에서 할수있는
배낭알고리즘을 통해 풀수있다.
높이에 따른 DP를 통해 문제해결이 가능하다.