DP
-
1932.정수 삼각형알고리즘/백준 BAEK JOON 2020. 8. 19. 21:37
이번에 풀어볼 문제는 백준 1932번 정수 삼각형이다. 1932번: 정수 삼각형 문제 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 위 그림은 크기가 5인 정수 삼각형의 한 모습이다. 맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최� www.acmicpc.net 정말 쉬워보이지만 자신의 인접한 대각선의 숫자로만 합을 구해야한다는 점을 해결해야만 이 문제를 풀 수 있다. 이 문제를 푸는 방법은 대표적으로 DP 동적계획법을 사용하는 것이다. * 제일 꼭대기의 값 부터 값을 누적해서 진행하되 겹치는 부분은 둘 중 큰 값으로 누적하면 된다 * 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 ..
-
1793.타일링알고리즘/백준 BAEK JOON 2020. 4. 20. 22:15
(*)이번문제는 백준에 있는 1793번 타일링이다. dp에 속하는 메모이제이션을 공부하기 좋은 문제이며 long long int보다 커서 출력이 어려울 때 구현하는 Big interger도 활용할 수 있는 문제이다. 이해하는데 좀 많은 시간이 걸린 것 같다. 재귀함수가 특히 나는 너무 헷갈린다..쩝.. 그래도 이해했으니 성공! 1793번: 타일링 문제 2×n 직사각형을 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. 입력 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 숫자 0 ≤ n ≤ 250이 주어진다. 출력 입력으로 주어지는 각각의 n마다, 2×n 직사각형을 채우는 방법의 ..