세리프 따라잡기
WEEK04 - TIL 알고리즘 간단 정리 [백준 9084, 11053] 본문
https://www.acmicpc.net/problem/9084
9084번: 동전
우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는
www.acmicpc.net
Q> 2,4원으로 8원 만들기
동전 0원은 항상/무조건 1가지의 방법으로 만들 수 있다.
- 4원짜리로 0원을 만드는 건 = 0개를 내면 만들 수 있음 = 1가지 방법
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| 0원 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0원+2원 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| 0원+2원+4원 | 1 | 0 | 1 | 0 | 2 | 0 | 2 | 0 | 3 |
→ dp[8] = dp[8-4] = dp[4] = 2 +1
2+2+2+2 / 2+2+4 / 4+4 이렇게 3가지
https://www.acmicpc.net/problem/11053
11053번: 가장 긴 증가하는 부분 수열
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이
www.acmicpc.net
최장 증가 수열, 정확히 최장 증가 부분 수열은 어떠한 수열에서 오름차순으로 증가하는 가장 긴 부분수열을 의미한다.
문제의 [10, 20, 10, 30, 20, 50] 이 있다면
| 10 | 20 | 10 | 30 | 20 | 50 |
| 1 | 2 | 1 | 3 | 2 | 4 |
10까지 10
20까지 10, 20
10까지 10
30까지 10, 20, 30
20까지 10, 20
50까지 10, 20, 30, 50
로 나타낼 수 있다!
정말 간단한 정리 끘..🙃
'SW사관학교 정글' 카테고리의 다른 글
| WEEK04 - TIL 리눅스 편집기 사용 간단 정리 (0) | 2022.04.26 |
|---|---|
| WEEK04 - TIL 그리디 알고리즘 (0) | 2022.04.25 |
| WEEK04 - TIL DP 구현 / defaultdict (0) | 2022.04.22 |
| WEEK04 - TIL 다이나믹 프로그래밍 (0) | 2022.04.22 |
| WEEK03 - TIL 위상정렬 (0) | 2022.04.21 |
'SW사관학교 정글' Related Articles
more
Comments