https://www.acmicpc.net/problem/11057

풀이

1. 이차원 배열로 생각

2. 식 세우기 … 다음과 같이 시도했지만 정답 도출 실패..
   ==> 답지 보고 다시 풀 예정

1
2

int d[n][l] : 자리수가 n 자리인 수의 마지막 수가 l인 오르막 수의 개수
d[n][l] = d[n-1][l] + (10-l)  ( l은 0~9 )

https://www.acmicpc.net/problem/10844

틀린 풀이

직접

길이가 1인 계단수

길이가 2인 계단수

…

를 하나하나 구해보니

길이가 n인 계단 수 = 길이가 n-1인 계단수 * 2 -1 이라는 규칙이 나왔다.

하지만 계속 채점 결과는 틀렸다고 나옴..

맞는 풀이

이차원 배열로 품

* D[i][j] : 길이 i, 마지막 숫자가 j인 계단 수의 개수
* D[N][L] : N자리 계단수 마지막수는 L인 계단수의 개수
* D[N][L] = D[N-1][L-1] + D[N-1][L+1] (L : 1~8)
* D[N][0] = D[N][1]
* D[N][9] = D[N-1][8]

https://www.acmicpc.net/problem/11052

풀이

d[n] = n개 팔아서 얻을 수 있는 최대 수익

따라서
max( p[i] + d[n-i] )
i는 1~n

https://www.acmicpc.net/problem/9095

풀이

재귀로 푸니 또 다시 런타임 에러.
그래서 재귀로 풀지 않음

핵심 : 가장 마지막에 1을 더하거나, 2를 더하거나, 3을 더하건

d[n] = d[n-1] + d[n-2] + d[n-3]

https://www.acmicpc.net/problem/11727

풀이

1. d(n) = d(n-1) + 2*d(n-2)
   

2. 재귀

https://www.acmicpc.net/problem/11726

풀이

1. d(n) = d(n-2) + n(n-1)

2. 재귀함수

   “왜 시간 초과?”

https://www.acmicpc.net/problem/1463

풀이

D[N] = N을 1로 만드는데 필요한 연산의 최솟값

N
​ -> N-3 -> ….. > 1 : 1 + D[N/3] ====1번

​ -> N-2 -> ….. > 1 : 1 + D[N/2] ====2번

​ -> N-1 -> ….. > 1 : 1 + D[N/1] ====3번

D[N] = min(1번, 2번, 3번)

정의

• 어떤 것을 결정해야 하는 순간, 가장 좋다고 생각하는 것을 선택하면서 답 찾는 알고리즘

Dynamic Programming과 비교

• DP : 어떤 상황에서 할수 있는 상황 모두 살펴보고 거기서 가장 좋은것 선택

• Greedy : 할수 있는 선택 중에 제일 좋다고 생각되는 것 하나 선택해서 정답 찾아감

단점

• 그 때 그 때는 최적일 수 있지만, 최종적으로는 최적이 아니 수도

1
2
3
4
5
6
7
8
9
10
11

ex)  12원을 1, 4, 5원으로 거슬러 줄 때, 

5원 2개, 1원 2개 --> 총 4개가 필요

but, 정답은 4원 3개!!!

DP로 풀어야해.

D[n] = n원을 거슬러 주는 동전의 최소 개수

min(D[n-1], D[n-4], D[n-5]) + 1 

그럼 언제 쓰나

• 지금 이 순간 가장 좋은 경우 선택하는 것이 최적일 때.

• 왜 그게 최적인지 증명해야함

• 그래서 가장 어려워

• 그래서 시험이나 대회에 나오면 가장 나중에 풀어

예제

문제

자연수 N이 주어지면,
N의 각 자릿수의 합을 구해서 return 하는 solution 함수를 만들어 주세요.

예를들어 N = 123이면 1 + 2 + 3 = 6을 return 하면 됩니다.

제한사항

* N의 범위 : 100,000,000 이하의 자연수 <br>

<입출력 예>

N — answer

123 — 6

987 — 24

입출력 예 설명


입출력 예 #1

문제의 예시와 같습니다.

입출력 예 #2

9 + 8 + 7 = 24이므로 24를 return 하면 됩니다.

풀이

1. 정수형으로 입력 받음

2. 입력 받음 정수형을 문자열형으로 변환 ( 자릿수 구하기 용이하기 때문 )

3. chatAt(i) 번째 - ‘ 0 ‘ 을 하면 그 자릿수가 나옴

4. 각각 더하면 결과값 나옴

개념

1. 987이 입력되면

2. ‘9’ - ‘0’ = 57 - 48 = 9

https://www.acmicpc.net/problem/1260

풀이

• 어레이리스트 생성
  • ArrayList[] a = (ArrayList[]) new ArrayList[n+1];
• DFS
  • dfs(x) : x를 방문
  • 한 정점에 연결된 정점들 중에
    • 방문하지 않았으면 방문
• BFS
  • 아직 방문 하지 않았고 현 위치에서 갈 수 있는 정점들을 모두 큐에 넣어
  • 큐에 넣을 때 방문했다고 체크

결과