문제

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



풀이


2차원 배열로 메모이제이션해야 되는 문제였다.

D[N][L]을 N자리수에서 끝자리가 L로 끝나는 수의 계단수의 가지수라고 한다면

N자리 수에서 끝자리가 2로 정해지면, D[N-1][1]과 D[N-1][3]을 구하면 된다.

이를 점화식으로 표현하면

D[N][L] = D[N-1][L-1] + D[N-1][L+1]




'알고리즘 > BaekJoon' 카테고리의 다른 글

[11052]붕어빵 판매하기  (0) 2017.01.11
[9095]1,2,3 더하기  (0) 2017.01.11
[11726]2 x n 타일링  (0) 2017.01.10
[3052]나머지(Modulo)  (0) 2017.01.02

문제

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


풀이

D[i]이 i개를 팔 때 얻을 수 있는 최대 수익

P[i]는 i개를 팔 때 얻는 수익


총 붕어빵이 i개 있을 때

1개를 팔았을 때 최대값은 P[1] + D[i-1]

2개를 팔았을 때 최대값은 P[2] + D[i-2]

j개를 팔았을 때 최대값은 P[j] + D[i-j]


이렇게 따져서 이들 값중에서 최대값이 D[i]

점화식을 살펴보면

D[i] = max(P[j] + P[i-j])

단, j의 범위는 1<= j <= i


이를 바탕으로 코딩을 해보면 된다.


#아직 프로그래밍적 사고와 다이나믹 프로그래밍적 문제 접근 방식이 익숙하지 않은것 같다.

'알고리즘 > BaekJoon' 카테고리의 다른 글

[10844]쉬운 계단 수  (0) 2017.01.13
[9095]1,2,3 더하기  (0) 2017.01.11
[11726]2 x n 타일링  (0) 2017.01.10
[3052]나머지(Modulo)  (0) 2017.01.02

문제

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


풀이

다이나믹 프로그래밍으로 풀 수 있었다.

n일때 1,2,3을 더해서 n을 표현하는 방법의 가지수를 d[n]이라고 한다.

마지막에 올 수 있는 숫자는 1, 2, 3 인데 

1이 오면 d[n-1]

2가 오면 d[n-2]

3이 오면 d[n-3] 이 성립된다.


이를 바탕으로 점화식을 세워보면

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


top-down 방식



bottom-up 방식


'알고리즘 > BaekJoon' 카테고리의 다른 글

[10844]쉬운 계단 수  (0) 2017.01.13
[11052]붕어빵 판매하기  (0) 2017.01.11
[11726]2 x n 타일링  (0) 2017.01.10
[3052]나머지(Modulo)  (0) 2017.01.02

문제

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


풀이

피보나치 수열과 같다.


bottom-up 방식으로 푸니까 런타임에러가 뜬다.


그래서 top-down방식으로 풀어봄


'알고리즘 > BaekJoon' 카테고리의 다른 글

[10844]쉬운 계단 수  (0) 2017.01.13
[11052]붕어빵 판매하기  (0) 2017.01.11
[9095]1,2,3 더하기  (0) 2017.01.11
[3052]나머지(Modulo)  (0) 2017.01.02

문제

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



풀이


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import java.util.Arrays;
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int count = 1;
        int[] remain = new int[10];
        for(int i=0;i<10;i++) {
            int num = scan.nextInt();
            remain[i] = num%42;
        }
        Arrays.sort(remain);
        for(int i=0; i<9; i++) {
            if(remain[i]!=remain[i+1]) {
                count++;
            }
        }
        
        System.out.println(count);
    }
}
cs


'알고리즘 > BaekJoon' 카테고리의 다른 글

[10844]쉬운 계단 수  (0) 2017.01.13
[11052]붕어빵 판매하기  (0) 2017.01.11
[9095]1,2,3 더하기  (0) 2017.01.11
[11726]2 x n 타일링  (0) 2017.01.10

+ Recent posts