https://www.acmicpc.net/problem/14226
14226번: 이모티콘
영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만
www.acmicpc.net
우선 입력되어있는 이모티콘 1개를 복사해서 계속 붙여나가는 시간을 계산하였습니다.
(dp[1]=0이지만 입력에 1이 주어지지 않기때문에 1로 하였습니다.)
그 다음은 클립보드에 이모티콘을 하나씩 늘려가면서 현재의 클립보드로 계속 이어나갈 경우,
현재의 클립보드로 이어나간 후 하나씩 삭제할 경우를 고려하여 계산하였습니다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 | #include <iostream> #include <algorithm> using namespace std; int dp[2001], clip; int func(int N) { dp[1] = 1; for (int i = 1; i <= 2000; i ++) { dp[i + 1] = dp[i] + 1; } clip = 2; while (clip <= 1001) { int r = dp[clip] + 2; dp[clip * 2] = min(dp[clip * 2], dp[clip] + 2); for (int i = clip * 3; i + clip <= 2000; i += clip) { dp[i] = min(dp[i], r + 1); r++; } for (int i = clip * 2 - 1; i >= clip + 1; i--) { dp[i] = min(dp[i], dp[i + 1] + 1); } clip++; } return dp[N]; } int main() { cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false); int N; cin >> N; cout << func(N) << '\n'; return 0; } | cs |
'algorithm > dp' 카테고리의 다른 글
| boj 12101 1, 2, 3 더하기 2 (0) | 2021.01.22 |
|---|---|
| boj 9095 1, 2, 3 더하기 (0) | 2021.01.22 |
| boj 17070 파이프 옮기기 1 (0) | 2021.01.22 |
| boj 11053 가장 긴 증가하는 부분 수열 (0) | 2021.01.22 |
| boj 1463 1로 만들기 (0) | 2021.01.22 |