Change-making problem
- 거스름돈 문제
- d1< d2 < ... < dm 인 동전의 가치를 갖는 동전들을 최소한으로 사용하여 금액 n을 거슬러준다.
- 예) 1, 3, 4원짜리만 있을 때 6원 만들기
Coin-Collecting problem
- n x m 좌판의 칸에 하나 이하의 동전이 배치됨
- 로봇은 좌상단부터 이동하여 가능한 많은 동전을 수집해야 함
- 로봇은 오른쪽 칸이나 아래쪽 칸으로만 이동 가능
조약돌 놓기
- 3×N 테이블의 각 칸에 양 또는 음의 정수가 기록되어 있다
- 조약돌을 놓는 방법 (제약조건)
- 각 열에는 적어도 하나의 조약돌을 놓아야 한다
- 가로나 세로로 인접한 두 칸에 동시에 조약돌을 놓을 수 없다
- 목표: 돌이 놓인 자리에 있는 수의 합을 최대가 되도록 조약돌 놓기
-
가능한 패턴
-
서로 양립할 수 있는 패턴
O(N)
행렬 경로 문제
- 양 또는 음의 정수 원소들로 구성된 n×n 행렬이 주어지고, 행렬의 좌상단에서 시작하여 우하단까지 이동한다
- 이동 방법 (제약조건)
- 오른쪽이나 아래쪽으로만 이동할 수 있다
- 왼쪽, 위쪽, 대각선 이동은 허용하지 않는다
- 목표: 행렬의 좌상단에서 시작하여 우하단까지 이동하되, 방문한 칸에 있는 수들을 더한 값이 최소화되도록 한다
O(N)
