반응형

1. 가장 처음 시작하는 시간과 가장 마지막에 끝나는 시간을 저장한다.

2. 그 시간동안 몇명이 들어와있는지 배열에 카운트 한다.

3. 개장 시작부터 마감시간 까지 파악하여 1일 경우 x1을  2일경우 x2를 3일경우 x3을 하여 더한다.


아래 사진은 카운트 예시이다.


arr[1] 은 트럭 한대 이기 때문에 +1이 arr[2]는 두대가 들어왔기 때문에 +2 arr[3]은 트럭 3대가 들어왔기 때문에 +3 의 값을 갖고 있다.

Switch 문을 통해 1,2,3을 구별하여 계산하면 된다. 아 끝~


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
import java.util.Scanner;
 
class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
 
        int A = sc.nextInt();
        int B = sc.nextInt();
        int C = sc.nextInt();
        int[] arr = new int[100];
        int start, end, max = 0;
        int min = 0;
        int sum = 0;
        for (int i = 0; i < 3; i++) {
            start = sc.nextInt();
            end = sc.nextInt();
            min = Math.min(min, start); //가장 빨리 시작하는 시간
            max = Math.max(max, end); //가장 늦게 끝나는 시간
            
            //트럭 한대의 start ~ end 시간동안 배열을 +1 해준다. 
            for (int j = start; j < end; j++) {
                arr[j]++;
            }
        }
        // 가장 처음 들어온 시간 부터 가장 마지막 시간 까지 계산을 한다.
        for (int i = min; i < max; i++) {
            switch (arr[i]) {
            case 1:
                sum = sum + A*arr[i];
                break;
            case 2:
                sum = sum + B*arr[i];
                break;
            case 3:
                sum = sum + C*arr[i];
                break;
            }
        }
        System.out.println(sum);
    }
 
}
cs


반응형
저작자표시

'나는요 공부가 좋....은걸... > 알고리즈음' 카테고리의 다른 글

[BOJ] 백준 1267 - 핸드폰 요금 (자바)  (0) 2018.02.05
[BOJ] 백준 1697 - 숨바꼭질 (자바)  (0) 2018.02.05
[BOJ] 백준 1012 - 유기농 배추 (자바)  (0) 2018.02.03
[BOJ] 백준 1475 - 방 번호 (자바)  (0) 2018.01.30
[BOJ] 백준 2178 - 미로찾기 (자바)  (0) 2018.01.23
반응형

윾기농 배추 문제

맨처음 런타임 에러가 나길래 뭐지 하고 문제를 다시 보니까

배추밭이 N*N이 아니라 N*M 이더라.... 

호다닥 수정하고 나니 정답!

+ BufferedReader를 사용했는데 String[] 배열을 통해서 값을 받아오는것 밖에 없나 싶더라.


풀이

1. 좌표 (0,0) 부터 (N,N) 까지 하나씩 살펴본다.

2. 배추가 있을경우(1일경우) DFS , BFS를 사용하여 상,하,좌,우에 배추도 같이 제거한다. (붙어있다면 한번에 제거 할 수 있기 때문)

3. 한번 수확하러 들어갈때마다 +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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
 
class Main {
    static int[] dx = { -1, 0, 1, 0 };
    static int[] dy = { 0, 1, 0, -1 };
    static int[][] arr;
    static int N;
    static int M;
 
    public static void main(String[] args) throws Exception {
        //BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt")));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        int T = Integer.parseInt(br.readLine());
        for (int Testcase = 0; Testcase < T; Testcase++) {
            String str[] = br.readLine().split(" ");
            M = Integer.parseInt(str[0]);
            N = Integer.parseInt(str[1]);
            int K = Integer.parseInt(str[2]);
            int count = 0;
            arr = new int[N][M];
            for (int i = 0; i < K; i++) {
                str = br.readLine().split(" ");
                arr[Integer.parseInt(str[1])][Integer.parseInt(str[0])] = 1;
            }
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    if (arr[i][j] != 0) {
                        DFS(i, j);
                        //배추 수확
                        count++;
                    }
                }
            }
 
            System.out.println(count);
 
        }
    }
 
    public static void DFS(int X, int Y) {
 
        for (int i = 0; i < 4; i++) {
            //다음 방문지 nextX,와 nextY
            int nextX = X + dx[i];
            int nextY = Y + dy[i];
 
            //nextX, nextY가 범위를 벗어난다면 그냥 통과한다.
            if (nextX < 0 || nextY < 0 || nextX >= N || nextY >= M) {
                continue;
            }
            //다음 방문할 값이 0 이라면 그냥 통과한다.
            if (arr[nextX][nextY] == 0) {
                continue;
            }
            //방문한점은 0으로 바꿔준다.
            arr[nextX][nextY] = 0;
            DFS(nextX, nextY);
        }
    }
 
}
cs


반응형
저작자표시

'나는요 공부가 좋....은걸... > 알고리즈음' 카테고리의 다른 글

[BOJ] 백준 1697 - 숨바꼭질 (자바)  (0) 2018.02.05
[BOJ] 백준 2979 - 트럭 주차 (자바)  (0) 2018.02.03
[BOJ] 백준 1475 - 방 번호 (자바)  (0) 2018.01.30
[BOJ] 백준 2178 - 미로찾기 (자바)  (0) 2018.01.23
[BOJ] 백준 5598 - 카이사르 (자바)  (0) 2018.01.22
반응형

6,9를 제외한 다른 숫자는 배열 카운트로 갯수를 저장하면된다.

6,9가 문제가 되는데 이때 6,9를 같은 숫자로 가정하여 계산을 한다.

6,9를 합쳐 반으로 나누면 되는데 합이 홀수 일때는 +1 을 해줘야한다.

예를들어) 6이 5번 9가 8번 사용하였을 때 둘의 합은 13이 되고 2로 나눌 경우 6이 되버린다.(정수이기 때문에)

             그래서 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
41
42
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
 
class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt")));
 
        String str = br.readLine();
 
        int size = str.length();
        int[] arr = new int[10];
        int temp = 0;
        int max = 0;
 
        //counting 배열을 사용하였다.
        for (int i = 0; i < size; i++) {
            temp = str.charAt(i) - '0';
            arr[temp]++;
 
        }
        //다른 숫자는 상관없지만 6,9일땐 바꿔서 사용가능하다.
        //6,9를 같은 숫자로 본다.
        int k = (arr[6] + arr[9]);
        //6,9의 합이 짝수이면 반으로 나누면 된다.
        if (k % 2 == 0) {
            arr[6] = k / 2;
            arr[9] = k / 2;
        }
        //6,9의 합이 홀수이면 반으로 나눠도 1번 더 사용해야되기 때문에 1을 더해준다.
        else {
            arr[6] = k / 2 + 1;
            arr[9] = k / 2 + 1;
        }
        //반복해서 최대값을 찾는다.
        for (int i : arr) {
            max = Math.max(max, i);
        }
        System.out.println(max);
    }
 
}
cs


반응형
저작자표시

'나는요 공부가 좋....은걸... > 알고리즈음' 카테고리의 다른 글

[BOJ] 백준 2979 - 트럭 주차 (자바)  (0) 2018.02.03
[BOJ] 백준 1012 - 유기농 배추 (자바)  (0) 2018.02.03
[BOJ] 백준 2178 - 미로찾기 (자바)  (0) 2018.01.23
[BOJ] 백준 5598 - 카이사르 (자바)  (0) 2018.01.22
[BOJ] 백준 2839 - 설탕배달 (자바)  (0) 2018.01.22
반응형

단순 BFS 문제이다. 

BFS 문제로는 어렵지 않다.

근데 나는 DFS로 풀고 싶은데 시간초과 안나게 어떻게 해야할지 모르겠다...

그리고 헷갈리는건 +1만 해주면 끝일까?  Queue를 이용하기 때문에 먼저 방문한게 조금더 최단거리일려나? 음음


BFS 해결방법

1. 다음 방문할 점을 큐에 넣는다.

2. 큐에서 빼온다음 다음 갈 곳이 조건에 벗어나지 않는다면 큐에 넣는다.

3. 큐가 빌때까지 계속한다. ( 내가 원하는 점에 왔을때 return 해줘도 가능하지 않을까? 개인적인 생각)


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
66
67
68
69
70
71
72
73
import java.io.FileInputStream;
import java.util.*;
 
public class Main {
 
    static int[][] arr;
    static boolean[][] visited;
    static int[] dx = { -1, 0, 1, 0 };
    static int[] dy = { 0, -1, 0, 1 };
    static int N;
    static int M;
 
    public static void main(String args[]) throws Exception {
        // Scanner sc = new Scanner(System.in);
        Scanner sc = new Scanner(new FileInputStream("input.txt"));
 
        N = sc.nextInt();
        M = sc.nextInt();
        sc.nextLine();
        arr = new int[N][M];
        visited = new boolean[N][M];
        for (int i = 0; i < N; i++) {
            String str = sc.nextLine();
            for (int j = 0; j < M; j++) {
                arr[i][j] = str.charAt(j)-'0';
                visited[i][j] = false;
            }
        }
        visited[0][0] = true;
        BFS(0, 0);
        System.out.println(arr[N - 1][M - 1]);
    }
 
    static public void BFS(int x, int y) {
 
        Queue<Dot> q = new LinkedList<Dot>();
        q.add(new Dot(x, y));
        //큐가 끝날때 까지
        while (!q.isEmpty()) {
            Dot d = q.poll();
            for (int i = 0; i < 4; i++) {
                //다음 방문할 좌표 nextX, nextY
                int nextX = d.x + dx[i];
                int nextY = d.y + dy[i];
                
                //다음 좌표가 범위를 넘어갈때 건너뛰기
                if (nextX < 0 || nextY < 0 || nextX >= N || nextY >= M) {
                    continue;
                }
                //이미 방문했던 점이면 건너뛰기
                if (visited[nextX][nextY] || arr[nextX][nextY] == 0) {
                    continue;
                }
                //다음에 방문할 좌표를 큐에 넣는다.
                q.add(new Dot(nextX, nextY));
                //배열안에 다음 방문할 곳은 현재 방문했던 점보다 1칸 더 가야하므로 +1
                arr[nextX][nextY] = arr[d.x][d.y] + 1;
                //다음 좌표는 방문했음으로 표시
                visited[nextX][nextY] = true;
            }
        }
    }
}
 
class Dot {
    int x;
    int y;
 
    Dot(int x, int y) {
        this.x = x;
        this.y = y;
    }
}
cs


반응형
저작자표시

'나는요 공부가 좋....은걸... > 알고리즈음' 카테고리의 다른 글

[BOJ] 백준 1012 - 유기농 배추 (자바)  (0) 2018.02.03
[BOJ] 백준 1475 - 방 번호 (자바)  (0) 2018.01.30
[BOJ] 백준 5598 - 카이사르 (자바)  (0) 2018.01.22
[BOJ] 백준 2839 - 설탕배달 (자바)  (0) 2018.01.22
[BOJ] 백준 10815 - 숫자카드 (자바)  (0) 2018.01.22
반응형

1. A,B,C의 입력과 나머지 입력의 차이점만 알면 쉽게 풀 수 있다.


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
import java.io.FileInputStream;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
 
public class Main {
 
    public static void main(String[] args) throws Exception {
        // TODO Auto-generated method stub
        Scanner sc = new Scanner(new FileInputStream("input.txt"));
        String str = sc.next();
 
        int size = str.length();
        int[] arr = new int[size];
        int[] decrypt = new int[size];
        for (int i = 0; i < size; i++) {
            arr[i] = str.charAt(i);
            //A,B,C의 입력은 X,Y,Z로 만들어 줘야하는데 앞으로 3칸을 땡기면 이상한 값이 출력방지하기 위해 + 23을 해준다.
            if(arr[i]-68<0){
                System.out.print((char)(arr[i]+23));
            }
            //ABC이외의 값들은 앞으로 3칸만 옮기면 된다.
            else{
                System.out.print((char)(arr[i]-3));
            }
            
        
        }
 
    }
 
}
 
cs


반응형
저작자표시

'나는요 공부가 좋....은걸... > 알고리즈음' 카테고리의 다른 글

[BOJ] 백준 1475 - 방 번호 (자바)  (0) 2018.01.30
[BOJ] 백준 2178 - 미로찾기 (자바)  (0) 2018.01.23
[BOJ] 백준 2839 - 설탕배달 (자바)  (0) 2018.01.22
[BOJ] 백준 10815 - 숫자카드 (자바)  (0) 2018.01.22
[BOJ] 백준 2751 - 수 정렬하기 2 (자바)  (0) 2018.01.19
반응형

정말 단순하면서 어려웠던 문제..


입력의 값이 크지 않기 때문에 반복문을 돌려도 된다.


1. 5로 나눠질때까지 계속 해서 3을 빼주면 된다. 또는 3으로 빼가면서 크기가 0보다 같거나 작아지면 종료한다.

2. 만약 처음값이 0보다 작은 값이면, 5던지 3이던지 나눠질 수 없는 값이다. 그런경우 -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
import java.io.FileInputStream;
import java.util.Scanner;
 
public class Main {
 
    public static void main(String[] args) throws Exception {
        // TODO Auto-generated method stub
        Scanner sc = new Scanner(new FileInputStream("input.txt"));
        // Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int five = 0;
        int three = 0;
        
        
        while(N%5!=0&&N>=0){
            N-=3;
            three++;
        }
        if(N<0){
            System.out.println(-1);
        }
        else{
            five = N/5;
            System.out.println(five+three);        
        }
    
    }
 
}
 
cs


반응형
저작자표시

'나는요 공부가 좋....은걸... > 알고리즈음' 카테고리의 다른 글

[BOJ] 백준 2178 - 미로찾기 (자바)  (0) 2018.01.23
[BOJ] 백준 5598 - 카이사르 (자바)  (0) 2018.01.22
[BOJ] 백준 10815 - 숫자카드 (자바)  (0) 2018.01.22
[BOJ] 백준 2751 - 수 정렬하기 2 (자바)  (0) 2018.01.19
[BOJ] 백준 2947 - 나무 조각 (자바)  (0) 2018.01.19
반응형

전체 탐색으로 하면 시간 초과가 날 것 같아서 HashSet를 사용했다.

또한, 중복된 수가 없었기 때문에 HashSet 사용이 가능했다.


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
import java.io.FileInputStream;
import java.util.HashSet;
import java.util.Scanner;
 
public class Main {
 
    public static void main(String[] args) throws Exception {
        // TODO Auto-generated method stub
        Scanner sc = new Scanner(new FileInputStream("input.txt"));
        // Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        HashSet<Integer> set = new HashSet<Integer>();
        for (int i = 0; i < N; i++) {
            set.add(sc.nextInt());
        }
 
        int M = sc.nextInt();
        for (int i = 0; i < M; i++) {
            if (set.contains(sc.nextInt())) {
                System.out.print(1);
            } else {
                System.out.print(0);
            }
            System.out.print(" ");
        }
    }
 
}
 
cs


반응형
저작자표시

'나는요 공부가 좋....은걸... > 알고리즈음' 카테고리의 다른 글

[BOJ] 백준 5598 - 카이사르 (자바)  (0) 2018.01.22
[BOJ] 백준 2839 - 설탕배달 (자바)  (0) 2018.01.22
[BOJ] 백준 2751 - 수 정렬하기 2 (자바)  (0) 2018.01.19
[BOJ] 백준 2947 - 나무 조각 (자바)  (0) 2018.01.19
[BOJ] 백준 2193 - 이친수 (자바)  (0) 2018.01.18
반응형

음수가 있는지 모르고 엄청 헤맨 문제;;


첫째 줄에 수의 개수 N(1<=N<=1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절대값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. 라는 문구를 제대로 이해하지 못했다.

즉, 음수도 가능하다는 얘기


그렇다면 음수와 양수를 어떻게 나눌 것인가에 대한 문제가 생긴다. 

배열 위치는 항상 양수만 가능하기 때문에 (arr[-900]같은 음수들은 존재 불가)

나는 0~1000000까지는 음수를 저장하는 변수로 1000001~2000000 은 양수를 저장하는 변수로 만들었다.

처음에 1000000을 더해주고 결과를 낼때는 1000000을 빼주면 된다.

예를들어) -1000000은 Arr[0]에 저장되고, 나올때 -1000000의 값을 빼기때문에 결과는 큰 상관이 없다.


그리고 Count Sorting을 이용하여 문제를 풀었다.



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
import java.io.FileInputStream;
import java.util.Scanner;
 
public class Main {
    public static void main(String args[]) throws Exception {
        // Scanner sc = new Scanner(System.in);
        Scanner sc = new Scanner(new FileInputStream("input.txt"));
 
        Integer a=  null;
        int N = sc.nextInt();
        int size = 2000000;
        int[] arr = new int[size + 5];
        for (int i = 1; i <= N; i++) {
            //Count Sorting... 해당 값의 위치를 1로 바꿔준다.
            //음수가 있기 때문에 1000000을 더해준다.
            arr[sc.nextInt() + 1000000] = 1;
        }
        for (int i = 0; i <= size; i++) {
            //모두 출력했는데 계속해서 반복문을 돌 수 있으니깐 N==0일때 종료되게 해준다.
            if(N==0) break;
            //Count Sorting이기 때문에 배열이 0이면 넘어간다. 
            if (arr[i] != 0) {
                System.out.println(i-1000000);
                N--;
            }
        }
    }
}
cs


반응형
저작자표시

'나는요 공부가 좋....은걸... > 알고리즈음' 카테고리의 다른 글

[BOJ] 백준 2839 - 설탕배달 (자바)  (0) 2018.01.22
[BOJ] 백준 10815 - 숫자카드 (자바)  (0) 2018.01.22
[BOJ] 백준 2947 - 나무 조각 (자바)  (0) 2018.01.19
[BOJ] 백준 2193 - 이친수 (자바)  (0) 2018.01.18
[BOJ] 백준 10825 - 국영수 (자바)  (0) 2018.01.13
반응형

문제에 나와있는대로 

1. 첫 번째 조각의 수가 두 번째 수보다 크다면, 둘의 위치를 서로 바꾼다.

2. 두 번째 조각의 수가 세 번째 수보다 크다면, 둘의 위치를 서로 바꾼다.

3. 세 번째 조각의 수가 네 번째 수보다 크다면, 둘의 위치를 서로 바꾼다.

4. 네 번째 조각의 수가 다섯 번째 수보다 크다면, 둘의 위치를 서로 바꾼다.

5. 만약 순서가 1, 2, 3, 4, 5 순서가 아니라면 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
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.io.FileInputStream;
import java.util.*;
 
public class Main {
    public static void main(String args[]) throws Exception {
        // Scanner sc = new Scanner(System.in);
        Scanner sc = new Scanner(new FileInputStream("input.txt"));
 
        int[] arr = new int[5];
        int[] answer = new int[5];
 
        for (int i = 0; i < 5; i++) {
            arr[i] = sc.nextInt();
        }
 
        while (check(arr)) {
            // 1vs2, 2vs3, 3vs4, 4vs5 비교
            for (int x = 0; x <= 3; x++) {
                // 앞의 숫자가 크고 정렬되지 않았다면 swap한다.
                if (compare(arr, x, x + 1) && check(arr)) {
                    swap(arr, x, x + 1);
                    print(arr);
                }
            }
        }
 
    }
 
    // x번째와 y번째 값 바꾸기
    public static void swap(int[] arr, int x, int y) {
        int swap;
        swap = arr[x];
        arr[x] = arr[y];
        arr[y] = swap;
    }
 
    // x번째와 y번째 값 비교하기
    public static boolean compare(int[] arr, int x, int y) {
        if (arr[x] > arr[y]) {
            return true;
        }
        return false;
    }
 
    // 나무조각 5개이기 때문에 1,2,3,4,5 로 정렬됐는지 체크
    public static boolean check(int[] arr) {
        boolean flags = false;
        for (int i = 0; i < 5; i++) {
            if (arr[i] != (i + 1)) {
                flags = true;
                break;
            }
        }
        return flags;
    }
    //출력문
    public static void print(int[] arr) {
        for (int i = 0; i < 5; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
 
    }
}
 
cs


반응형
저작자표시

'나는요 공부가 좋....은걸... > 알고리즈음' 카테고리의 다른 글

[BOJ] 백준 10815 - 숫자카드 (자바)  (0) 2018.01.22
[BOJ] 백준 2751 - 수 정렬하기 2 (자바)  (0) 2018.01.19
[BOJ] 백준 2193 - 이친수 (자바)  (0) 2018.01.18
[BOJ] 백준 10825 - 국영수 (자바)  (0) 2018.01.13
[BOJ] 백준 2399 - 거리의 차이 (자바)  (0) 2018.01.13
반응형

1자리 수 일때는 1 만 올 수 있다. (1개)

2자리 수 일때는 10 만 올 수 있다. (1개)

3자리 수 일때는 101, 100 이 올 수 있다. (2개)

4자리 수 일때는 1010, 1000, 1001 이 올 수 있다. (3개)

5자리 수 일때는 10100, 10101, 10000, 10001, 10010 이 올 수 있다. (5개)

6자리 수 일때는 101000, 101001, 101010, 100000, 100001, 100010, 100100, 100101 이 올 수 있다. (8개)


어느 정도 규칙이 보이지 않는가? 1 - 1 - 2- 3- 5- 8 - ???

안 보인다면 7자리 수일떄도 해보겠다.


1010000, 1010001, 1010010, 1010100, 1010101, 1000000, 1000001, 1000010, 1000100, 1000101, 1001000, 1001001, 1001010 (13개)


이정도면 보였으리라 생각한다. 피보나치의 규칙을 갖고 있다.

피보나치의 규칙을 이용해서 문제를 풀면 끝!


사실 이문제는 끝자리가 0으로 끝나는 dp[N][0], 1로 끝나는 dp[N][1] 로 푸는게 맞다.

앞의 수가 0일때는 0,1이 둘다 올수 있고 앞의수가 1일때는 0밖에 못오니깐..

아무튼 쉬운 경로로 풀면 되긴 하지만, 좀 더 직관적으로 보이는 뒤의 방법을 이용하는 것이 좋아보인다.



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import java.io.FileInputStream;
import java.util.*;
public class Main {
    public static void main(String args[]) throws Exception {
        // Scanner sc = new Scanner(System.in);
        Scanner sc = new Scanner(new FileInputStream("input.txt"));
        int N = sc.nextInt();
        int[] arr = new int[N];
        if (N == 1) {
            arr[0] = 1;
        } else if (N == 2) {
            arr[1] = 1;
        } else {
            arr[0] = 1;
            arr[1] = 1;
            for (int i = 2; i < N; i++) {
                arr[i] = arr[i - 1] + arr[i - 2];
            }
        }
        System.out.println(arr[N-1]);
    }
}
 
cs


반응형
저작자표시

'나는요 공부가 좋....은걸... > 알고리즈음' 카테고리의 다른 글

[BOJ] 백준 2751 - 수 정렬하기 2 (자바)  (0) 2018.01.19
[BOJ] 백준 2947 - 나무 조각 (자바)  (0) 2018.01.19
[BOJ] 백준 10825 - 국영수 (자바)  (0) 2018.01.13
[BOJ] 백준 2399 - 거리의 차이 (자바)  (0) 2018.01.13
[BOJ] 백준 11651 - 좌표 정렬하기 (자바)  (0) 2018.01.12

+ Recent posts

티스토리툴바