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
package n11057;
 
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
 
        int n = sc.nextInt();
        long[][] dp = new long[n+1][11];
 
        for(int i = 0; i < 10; i++){
            dp[1][i] = 1;
        }
 
        for(int i = 2; i < n+1; i++){
            for(int j = 0; j < 10; j++){
                for(int k = 0; k < 10; k++){
                    if( j - k >= 0){
                        dp[i][j] += dp[i-1][j-k];
                    }
                }
//                dp[i][j] += dp[i-1][j];
                dp[i][j] %= 10007;
            }
        }
 
        long result = 0;
        for(int i = 0; i<10; i++){
            result += dp[n][i];
        }
        result = result%10007;
        System.out.println(result);
    }
}
 
cs


저작자표시 비영리

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

[code.plus 알고리즘 기초] no. 10844  (0) 2019.01.23
[code.plus 알고리즘 기초] no. 2193  (0) 2019.01.22
[code.plus 알고리즘 기초] no. 11052  (0) 2019.01.21
[code.plus 알고리즘 기초] no. 9095  (0) 2019.01.19
[code.plus 알고리즘 기초] no. 11727  (0) 2019.01.17

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



잘못된 방법




올바른 방법


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
package n10844;
 
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[][] dp = new long[n+1][10];
 
        for(int i = 1; i<=9; i++){ // n이 1일때 마지막 숫자(i)가 나올 경우의 수 n이 1이기 때문에 당연히 전부 1이다.
            dp[1][i] = 1;
        }
 
        for(int i = 2; i < n+1; i++){
            for(int j = 0; j <= 9; j++){ // j는 마지막 숫자를 나타냄
                if(j >= 1){ // 1보다 크면
                    dp[i][j] += dp[i-1][j-1]; //마지막숫자(j) 보다 1작은 숫자의 경우의 수를 더해주고
                }
                if(j <= 8){ // 8보다 작으면
                    dp[i][j] += dp[i-1][j+1]; //마지막숫자(j) 보다 1큰 숫자의 경우의 수를 더해주고
                }
                dp[i][j] = dp[i][j] % 1000000000; // 마지막 dp[]의 결과에는 10억을 나눠주고 나머지값을 저장한다.
            }
        }
 
        long result = 0;
        for (int i=0; i<=9; i++) {
            result += dp[n][i];
        }
        result %= 1000000000;
 
        System.out.println(result);
    }
}
 
cs


저작자표시 비영리

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

[code.plus 알고리즘 기초] no. 11057  (0) 2019.01.25
[code.plus 알고리즘 기초] no. 2193  (0) 2019.01.22
[code.plus 알고리즘 기초] no. 11052  (0) 2019.01.21
[code.plus 알고리즘 기초] no. 9095  (0) 2019.01.19
[code.plus 알고리즘 기초] no. 11727  (0) 2019.01.17

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



내가 쓴 방법


또 다른 방법


주의사항

90번째 피보나치 수의 크기?

double 써도 안됨


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
package n2193;
 
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
 
        long[] o; // count of one
        long[] z; // count of zero
 
        int n = sc.nextInt();
        o = new long[n+1];
        z = new long[n+1];
 
        long result = 1;
 
        o[1] = 1;
        z[1] = 0;
        for(int i = 2; i< n+1; i++){
            z[i] = z[i-1] + o[i-1];
            o[i] = z[i-1];
        }
        result = z[n] + o[n];
 
        System.out.println(result);
    }
}
 
cs


저작자표시 비영리

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

[code.plus 알고리즘 기초] no. 11057  (0) 2019.01.25
[code.plus 알고리즘 기초] no. 10844  (0) 2019.01.23
[code.plus 알고리즘 기초] no. 11052  (0) 2019.01.21
[code.plus 알고리즘 기초] no. 9095  (0) 2019.01.19
[code.plus 알고리즘 기초] no. 11727  (0) 2019.01.17

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



좋지 못한 접근 방법

dp(dynamic programming)문제는 이전의 있는 값을 활용해서 풀어야한다.

무턱대고 직관적인 방식으로 풀다가는 꼬이기도 쉽고 런타임 시간과 푸는 시간도 오래 걸릴 것이다.



올바른 접근 방법



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
package n11052;
 
import java.util.Scanner;
 
public class Main {
    public static int result = 0;
 
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n+1]; // price 배열
 
        for (int i=1; i<=n; i++) {
            a[i] = sc.nextInt();
        }
 
        int[] d = new int[n+1]; // 최대값 저장
 
        for (int i=1; i<=n; i++) {
            for (int j=1; j<=i; j++) {//dp[n]을 max값 비교하기 위해 총 n번 검사
                if (d[i] < d[i-j] + a[j]) { // max 값 비교
                    d[i] = d[i-j] + a[j];// 사는 경우의 수( 카드를 1개 살때부터 n개 살때까지
                }
            }
        }
        System.out.println(d[n]);
    }
}
 
cs


저작자표시 비영리

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

[code.plus 알고리즘 기초] no. 10844  (0) 2019.01.23
[code.plus 알고리즘 기초] no. 2193  (0) 2019.01.22
[code.plus 알고리즘 기초] no. 9095  (0) 2019.01.19
[code.plus 알고리즘 기초] no. 11727  (0) 2019.01.17
[code.plus 알고리즘 기초] no. 11726  (0) 2019.01.16

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



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
package n9095;
 
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int[] dp;
        int T = sc.nextInt();
        while(T-- > 0){
            int n = sc.nextInt();
            dp = new int[n+1];
            dp[0] = 0;
            if( n == 1 || n == 2){
                dp[n] = n;
            }else if(n == 3){
                dp[n] = 4;
            }else if( n > 3){
                dp[1] = 1;
                dp[2] = 2;
                dp[3] = 4;
                for(int i = 4; i<=n; i++){
                    dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
                }
            }
            System.out.println(dp[n]);
        }
    }
}
 
cs


저작자표시 비영리

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

[code.plus 알고리즘 기초] no. 2193  (0) 2019.01.22
[code.plus 알고리즘 기초] no. 11052  (0) 2019.01.21
[code.plus 알고리즘 기초] no. 11727  (0) 2019.01.17
[code.plus 알고리즘 기초] no. 11726  (0) 2019.01.16
[code.plus 알고리즘 기초]no. 1463  (0) 2019.01.16

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


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
package n11727;
 
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
 
        int n = sc.nextInt();
        int[] dp = new int[n+1];
        dp[0] = 1;
        dp[1] = 1;
        for(int i =2; i<=n; i++){
            dp[i] = dp[i-1] + dp[i-2] + dp[i-2];
            dp[i] %= 10007;
        }
        System.out.println(dp[n]);
 
    }
}
 
cs


저작자표시 비영리

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

[code.plus 알고리즘 기초] no. 11052  (0) 2019.01.21
[code.plus 알고리즘 기초] no. 9095  (0) 2019.01.19
[code.plus 알고리즘 기초] no. 11726  (0) 2019.01.16
[code.plus 알고리즘 기초]no. 1463  (0) 2019.01.16
[code.plus 알고리즘 기초]no. 1158  (0) 2019.01.14



좋지 못한 예

문제 푸는 도중 규칙을 찾고서 빠르게 푸려고 하는 방식은 좋다. 

그러나 규칙만 찾고 그 원리에 대해서 이 규칙을 100% 적용해도 되는 걸까? 라고 다시한번 생각해보길 바란다.


제대로 된 풀이



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
package n11726;
 
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int[] dp;
 
        int n = sc.nextInt();
        dp = new int[n+1];
 
        dp[0] = 1;
        dp[1] = 1;
        for(int i = 2; i<=n; i++){
            dp[i] = dp[i-1] + dp[i-2];
            dp[i] %= 10007;
        }
 
        System.out.println(dp[n]);
    }
}
 
cs




저작자표시 비영리

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

[code.plus 알고리즘 기초] no. 9095  (0) 2019.01.19
[code.plus 알고리즘 기초] no. 11727  (0) 2019.01.17
[code.plus 알고리즘 기초]no. 1463  (0) 2019.01.16
[code.plus 알고리즘 기초]no. 1158  (0) 2019.01.14
[code.plus 알고리즘 기초]no. 10799  (0) 2019.01.13


top-down 방식

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
41
42
43
package n1463;
 
import java.util.Scanner;
 
public class Main {
    public static int[] dp;//dp[n]은 n을 1로 만드는데 필요한 연산의 최소값
 
    public static int procCnt(int n){
//        System.out.println(n);
//        for(int i = 0; i< dp.length; i++){
//            System.out.print(dp[i]+",");
//        }
        if(n == 1){ // 1이 들어올 때는 연산이 필요없음
            return 0;
        }
        if(dp[n] > 0){ // memorization 어차피 같은 연산이면 연산하지 않도록 하게
            return dp[n];
        }
        dp[n] = procCnt(n-1)+1;
        if(n%2 == 0){
            int temp = procCnt(n/2)+1; // n/2로 해서 리턴 받은 값을 temp에 저장
            if(dp[n] > temp){ //  temp가 dp[n]보다 작다면 dp[n]을 temp로 바꿔준다.
                dp[n] = temp;
            }
        }
        if(n%3 == 0){
            int temp = procCnt(n/3)+1;
            if(dp[n] > temp){
                dp[n] = temp;
            }
        }
 
        return dp[n];
 
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int X = sc.nextInt();
        dp = new int[X+1];
        System.out.print(procCnt(X));
    }
}
 
cs


bottom-up방식

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import java.util.*;
 
public class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] d = new int[n+1];
        d[1] = 0;
        for (int i=2; i<=n; i++) {
            d[i] = d[i-1] + 1;
            if (i%2 == 0 && d[i] > d[i/2] + 1) {
                d[i] = d[i/2] + 1;
            }
            if (i%3 == 0 && d[i] > d[i/3] + 1) {
                d[i] = d[i/3] + 1;
            }
        }
        System.out.println(d[n]);
    }
}
cs


저작자표시 비영리

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

[code.plus 알고리즘 기초] no. 11727  (0) 2019.01.17
[code.plus 알고리즘 기초] no. 11726  (0) 2019.01.16
[code.plus 알고리즘 기초]no. 1158  (0) 2019.01.14
[code.plus 알고리즘 기초]no. 10799  (0) 2019.01.13
[code.plus 알고리즘 기초]no. 9012  (0) 2019.01.13



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
package n1158;
 
import java.util.Scanner;
import java.util.Queue;
import java.util.LinkedList;
 
public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
 
        int n = 0;
        int m = 0;
 
        n = sc.nextInt();
        m = sc.nextInt();
 
        Queue<Integer> q = new LinkedList<Integer>();
 
        for(int i = 1; i<=n; i++){
            q.offer(i);
        }
 
        System.out.print("<");
        for(int i = 0; i < n - 1; i++){
            for(int j = 0; j < m - 1; j++){
                q.offer(q.poll());
            }
            System.out.print(Integer.toString(q.poll()) + ", ");
        }
        System.out.print(Integer.toString(q.poll()) + ">");
    }
}
 
cs


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

[code.plus 알고리즘 기초] no. 11727  (0) 2019.01.17
[code.plus 알고리즘 기초] no. 11726  (0) 2019.01.16
[code.plus 알고리즘 기초]no. 1463  (0) 2019.01.16
[code.plus 알고리즘 기초]no. 10799  (0) 2019.01.13
[code.plus 알고리즘 기초]no. 9012  (0) 2019.01.13

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





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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
import java.util.Scanner;
 
class Stack{
    private int[] stack;
    private int top;
    private int defaultData = -999;
 
    Stack(int lenght){
        this.stack = new int[lenght];
        for(int i = 0; i<this.stack.length; i++){
            this.stack[i] = defaultData;
        }
        this.top = 0;
    }
 
    void push(int data){
        this.stack[this.top] = data;
        this.top++;
//        System.out.println("push: "+top);
    }
 
    int pop(){
        this.top--;
        int data = this.stack[top];
        this.stack[top] = defaultData;
//        System.out.println("pop: "+top);
 
        return data;
    }
 
    int getSize(){
        return this.top;
    }
 
}
 
public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
 
        String str = sc.nextLine();
        char[] c = str.toCharArray();
 
        Stack st = new Stack(c.length);
        int result = 0;
 
        for(int i = 0; i<c.length; i++){
            if(c[i] == '('){
                st.push(i); // 여는 괄호의 index값을 stack에 넣는다.
            }else{ //닫는 괄호에서
                if(i - st.pop() == 1) { // 현재 i의 값(닫는 괄호의 index)와 마지막으로 넣은 여는 괄호의 index의 차이가 1이라면
//                    System.out.println("i-x = 1");
                    result += st.getSize(); // 현재 stack의 사이즈를 result에 더해준다.
                }
                else{ // 이 부분 조심. 위의 if중에 함수 실행하는 명령어가 포함되어 있으면 else문에서도 함수가 실행됨. (현재: st.pop()이 실행됬음.)
//                    System.out.println("i-x != 1");
//                    st.pop();
                    result+=1;
                }
            }
        }
        System.out.println(result);
    }
}
 
cs


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

[code.plus 알고리즘 기초] no. 11727  (0) 2019.01.17
[code.plus 알고리즘 기초] no. 11726  (0) 2019.01.16
[code.plus 알고리즘 기초]no. 1463  (0) 2019.01.16
[code.plus 알고리즘 기초]no. 1158  (0) 2019.01.14
[code.plus 알고리즘 기초]no. 9012  (0) 2019.01.13

+ Recent posts

티스토리툴바