소스 보러가기
문제 보러가기


사용한 알고리즘 및 자료구조
Sol 1 : ArrayList, Sol 2 : Stack

풀이
따로 알고리즘 구현이 필요 없는 문제이다. ArrayList, List, Stack 과 같은 자료구조 개념을 알고 있다면 쉽게 풀 수 있는 문제이다.

  1. 열 순서대로 인형 탐색

  2. 인형 있으면 -> 해당 칸 빈칸으로

  3. Stack or List 마지막 칸과 비교 같으면 삭제 후 정답 카운트 증가
    다르면 맨 뒤에 추가

  4. moves배열의 길이만큼 수행했다면 정답 카운트 출력

상당히 간단하다. Stack, List 둘다 가능할 것이라 생각하여 solution을 2개 만들었다.

로직은 같고 차이점은 Stack은 뽑는 행위가 디폴트 값으로 마지막 위치에 인형을 뽑는다. 그리고List는 (인덱스 값-1)을 매개변수로 get()을 이용하여 바구니 마지막 위치에 있는 인형을 출력한다.

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
74
75
76
// before test, have to delete 'static' keywords
    public static int solution(int[][] board, int[] moves) {
        int answer = 0;
 
        ArrayList<Integer> box = new ArrayList<Integer>();
 
        for (int idx = 0; idx < moves.length; idx++) {
 
            int row = moves[idx] - 1;
 
            for (int col = 0; col < board.length; col++) {
 
                int boxLastIdx = box.size() - 1;
 
                if (board[col][row] != 0) {
 
                    if (box.isEmpty()) {
                        box.add(board[col][row]);
                    } else {
 
                        if (box.get(boxLastIdx) == board[col][row]) {
 
                            box.remove(boxLastIdx);
                            answer += 2;
                        } else {
                            box.add(board[col][row]);
                        }
 
                    }
                    board[col][row] = 0;
 
                    break;
 
                }
 
            }
 
        }
 
        return answer;
    }
    
 
    public int solution2(int[][] board, int[] moves) {
        Stack<Integer> box = new Stack<Integer>();
 
        int answer = 0;
        for (int i = 0; i < moves.length; i++) {
            int row = moves[i];
            for (int col = 0; col < board.length; col++) {
                if (board[col][row - 1!= 0) {
 
                    if (box.empty()) {
                        box.push(board[col][row-1]);
                    } else {
 
                        if (box.peek() == board[col][row-1]) {
                            box.pop();
                            answer += 2;
                        } else {
 
                            box.push(board[col][row-1]);
                        }
 
                    }
                    board[col][row-1= 0;
 
                    break;
                }
 
            }
 
        }
 
        return answer;
    }
cs

'알고리즘(추가예정) > 기타' 카테고리의 다른 글

[프로그래머스] 베스트앨범  (0) 2020.08.30

소스 보러가기
문제 보러가기


사용한 알고리즘 및 자료구조
DP

풀이
처음에 설계를 올바르게 하지 못해 상당히 시간이 걸렸다. 30분정도 진행하다가 이내 잘 못 되었다는 것을 깨닫고 다시 설계를 해서 10분만에 끝냈다.
숫자 3개와 뭔가 규칙성이 있다는 것을 알고 있었지만, 이것을 3의 지수승으로 접근했다. 하지만 숫자에 따라서 3으로 나누면 나머지가 0,1,2가 된다는 것을 알게 되었다. 단, 1,2,4로 표현을 해야되기 때문에 나머지가 0일때는 4를 문자열에 더해주면 된다.

너무 어렵게 생각하면 독이 된다는 것을 가르쳐준 문제였다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
    public static String solution(int n) {
 
        String answer = "";
 
        int mod;
 
        while (n > 0) {
 
            mod = n % 3;
            n /= 3;
 
            if (mod == 0) {
                n -= 1;
                mod = 4;
            }
 
            answer += String.valueOf(mod);
 
        }
 
        return answer;
 
    }
cs

'알고리즘(추가예정) > 동적계획법' 카테고리의 다른 글

[프로그래머스] 네트워크  (0) 2020.08.23
[프로그래머스] 2n 타일링  (0) 2020.08.23
백준 2315 가로등 끄기  (0) 2017.11.16
백준 1563 개근상  (0) 2017.11.14
백준 1495 기타리스트  (0) 2017.11.13

소스 보러가기
문제 보러가기


사용한 알고리즘 및 자료구조

HashMap,ArrayList

풀이
문제를 보고 HashMap 사용을 떠올랐다. 가장 먼저 생각한 것은 자바의 콜렉션을 최소화 하여 문제를 풀어내는 것 이었다. 그리고 총 4개의 콜렉션을 사용하여 문제를 풀었다.

먼저 파악해야 될 것은 정렬의 우선순위 요소 파악이다.

“장르 우선순위 , 노래 재생 횟수, 고유번호가 낮은 순서” 이렇게 우선순위가 선정되어 정렬이 된다. 파악한 우선순위로 차례차례 문제를 풀면 간단히 해결이 된다.

  1. 각 장르별로 재생된 횟수 구하여 HashMap에 담기

  2. 노래에 대한 구조체를 만들어 ArrayList에 담기

  3. 정렬하기 : Collections.sort() 함수 이용

  4. 정렬된 ArrayList에서 장르별 순서대로 2개씩 노래 새로운 ArrayList에 담기

간단하게 표현하면 이렇게 4단계로 문제가 풀린다. 자세한건 코드를 보면서 파악하기 바란다.

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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
    // before test, have to delete 'static' keywords
    public static int[] solution(String[] genres, int[] plays) {
        HashMap<String, Integer> genresCheck = new HashMap<String, Integer>();
        HashMap<String, Integer> inputCheck = new HashMap<String, Integer>();
        ArrayList<Song> songList = new ArrayList<Song>();
        ArrayList<Integer> outputList = new ArrayList<Integer>();
        //1. genres count
        
        
        
        for(int g_idx = 0; g_idx < genres.length; g_idx++) {
 
            String g_str = genres[g_idx];
            songList.add(new Song(g_str,plays[g_idx],g_idx));
            
            if(genresCheck.containsKey(g_str)) {
                genresCheck.put(g_str, genresCheck.get(g_str)+plays[g_idx]);
            } else {
                
                genresCheck.put(g_str, plays[g_idx]);
            }
            
        }
        //2. sort
        
        Collections.sort(songList, new Comparator<Song>() {
            
            //s1 new
            @Override
            public int compare(Song s1, Song s2) {
                
                if(s1.genresName.equals(s2.genresName)) {
                    
                    if(s1.playCount != s2.playCount) {
                        return - (s1.playCount - s2.playCount);
                    } else {
                        
                        return (s1.songNum - s2.songNum);
                    }
                    
                } else {
                    
                    return -(genresCheck.get(s1.genresName) - genresCheck.get(s2.genresName));
                    
                }
                
            }
            
            
        }); 
        //3.checking
        for(int idx = 0; idx < songList.size(); idx++) {
            
            Song song = songList.get(idx);
            
            if(!inputCheck.containsKey(song.genresName)) {
                inputCheck.put(song.genresName, 1);
                outputList.add(song.songNum);
            } else {
                
                int cnt = inputCheck.get(song.genresName);
                
                if(cnt > 1) {
                    continue;
                } else {
                    inputCheck.put(song.genresName, cnt+1);
                    outputList.add(song.songNum);
 
                }
                
            }
            
        }
        
        int[] answer = new int[outputList.size()];
        
        for(int s_idx = 0; s_idx < answer.length; s_idx++) {
            answer[s_idx] = outputList.get(s_idx);
        }
 
 
        return answer;
    }
 
    static class Song {
        
        String genresName;
        int playCount;
        int songNum;
 
        public Song(String genresName, int playCount, int songNum) {
            
            this.genresName = genresName;
            this.playCount = playCount;
            this.songNum = songNum;
 
        }
 
    }
 
cs

'알고리즘(추가예정) > 기타' 카테고리의 다른 글

[프로그래머스] 인형뽑기  (0) 2020.08.30

소스 보러가기
문제 보러가기


사용한 알고리즘 및 자료구조
DFS/BFS, 그래프

풀이

간단한 DFS/BFS 문제이다. 문제를 푸는데 20분도 안 걸렸다. 이번에는 DFS를 이용해서 해당 문제를 풀었다. 이 문제를 읽고 생각을 했던 것은 2차원 배열에서 (n,n) 칸들을 기준으로 좌우 대칭이 된다는 것이다. 또한 각각의 값들이 연결관계를 표현했다. 따라서 처음에 탐색할 때는 1/2만 탐색을 하고 DFS 를 사용할 때는 연결관계를 기준으로 탐색을 하면 된다. 보통의 DFS 문제는 ‘상하좌우’로 움직이면서 문제를 해결했지만, 해당 문제는 배열의 값들이 내포하고 있는 연결관계를 이용해서 DFS 함수를 구현했다.

  1. 초기화
  2. 문제에 해당하는 조건( 배열의 값 : 1 && 아직 탐색하지 않은 칸) 찾기 ,조건을 찾을 때 마다 answer++
  3. 조건 찾고 나서 DFS 함수를 이용해 연결관계를 따라 영역표시하기
  4. 다시 2-3번 반복
  5. Answer 출력

간단한 DFS 문제이다. 실제로 삼성 시험을 봤던 사람들에게는 매우 쉬웠을 거라 생각한다. 다만 이것을 어떻게 해야 더 효율적으로 구현할 수 있을까 고민해보았다. 간단한 문제라 특별하게 적용할 것은 없었으나, 그래도 고민 해보면 좋을 것이다.

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
    public static int SIZE;
 
    // before test, have to delete 'static' keywords
    public static int solution(int n, int[][] computers) {
        int answer = 0;
        boolean[][] visited = new boolean[n][n];
        SIZE = n;
 
        for (int c_idx = 0; c_idx < n; c_idx++)
            for (int r_idx = c_idx; r_idx < n; r_idx++) {
 
                if ((computers[c_idx][r_idx] == 1&& (visited[c_idx][r_idx] == false)) {
                    visited[c_idx][r_idx] = true;
                    dfs(r_idx, visited, computers);
                    answer++;
 
                }
            }
 
        return answer;
    }
 
    public static void dfs(int idx, boolean[][] visited, int[][] computers) {
 
        for (int col = 0; col < SIZE; col++) {
 
            if ((computers[idx][col] == 1&& (visited[idx][col] == false)) {
 
                visited[idx][col] = true;
 
                dfs(col, visited, computers);
 
            }
 
        }
 
    }
 
 
cs

'알고리즘(추가예정) > 동적계획법' 카테고리의 다른 글

[프로그래머스] 124 나라의 숫자  (0) 2020.08.30
[프로그래머스] 2n 타일링  (0) 2020.08.23
백준 2315 가로등 끄기  (0) 2017.11.16
백준 1563 개근상  (0) 2017.11.14
백준 1495 기타리스트  (0) 2017.11.13

소스 보러가기
문제 보러가기


사용한 알고리즘 및 자료구조

DP , 피보나치

풀이

문제에 대한 접근 방향이 중요하다. 여러 접근에 대한 후보를 떠올리고 최적의 후보를 택하여 접근해보았다. 인덱스 순서대로 접근하려고 했으나, 이내 방향을 바꿔 가장 맨 뒤를 가정하고 접근했다.

내가 N일 때, N-1, N-2에 올 수 있는 모양에 대해서 생각해보면 된다.

  • N-1 일 때 : 블록을 세울 수 밖에 없다.

  • N-2 일 때 : 세로 블록 2개 , 가로 블록 2개인 경우로 나뉠 수 있다. 하지만 세로 블록 2개인 경우에 N-1인 경우와 같다. 따라서 가로 블록 2개인 경우만 카운팅 된다.

즉, N-1, N-2가 어떠한 블록이 오느냐에 따라서 자동으로 N번째까지 블록이 채워진다.

그러므로 N-1 + N-2 개수를 합하여 더 하면 된다.

N = (N-1)+(N-2) => 피보나치

규칙을 보면 피보나치 수열이 근간이 되어 풀리는 문제다. 자세한건 코드를 보면서 파악하기 바란다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
    public static int solution(int n) {
        int answer = 0;
        int s = 1000000007;
 
        int[] dp = new int[n + 1];
 
        dp[0= 0;
        dp[1= 1;
        dp[2= 2;
 
        for (int idx = 3; idx <= n; idx++) {
 
            dp[idx] = (dp[idx - 2+ dp[idx - 1]) % s;
 
        }
 
        answer = dp[n];
 
        return answer;
    }
 
 
cs

'알고리즘(추가예정) > 동적계획법' 카테고리의 다른 글

[프로그래머스] 124 나라의 숫자  (0) 2020.08.30
[프로그래머스] 네트워크  (0) 2020.08.23
백준 2315 가로등 끄기  (0) 2017.11.16
백준 1563 개근상  (0) 2017.11.14
백준 1495 기타리스트  (0) 2017.11.13


문제보기


상당히 오래 걸렸다. 

백준강의 자료를 참고해서 완성할 수 있었다. 


마징가는 태권V덕분에 가로등만 끄면 되는 편한일(?)을 맡았다는 내용,


마징가의 움직임에 살펴보자 마징가는 현재 '5'번의 위치하고 있다. 

그리고 끄려면 수평으로 움직여야 한다. 

그렇다면 어떻게 움직일 수 있는가 ? 

좌우로 움직이면 된다. 

그리고 생각해보면 만약 두칸을 움직여서 끄면 건너뛴 가로등을 다시 꺼야되는

일이 발생한다. 

두번 일하지 말고, 가면서 만나는 가로등은 다 끄도록하자.

결국

좌우로 움직이게 되고 가로등을 끄면서 켜져있는 값들을 더하면서 나가면된다. 


점화식은 

if(left - 1 >= 1) {

ans = Math.min(ans, solution(left-1,right,0) + (a[now]-a[left-1])*(s[n]-s[right]+s[left-1]));

} 

if(right + 1 <=n) {

ans = Math.min(ans, solution(left,right+1,1) + (a[right+1]-a[now])*(s[n]-s[right]+s[left-1]));

}


이렇게 된다 왼쪽으로 움직이는 경우 마지막 index 1번까지 갈 수 있고 ,

오른쪽으로 움직이는 경우 마지막은 n까지 갈 수 있다. 

그리고 왼쪽으로 움직인경우 index를 이동해야하기 때문에 left-1, 오른쪽은 right+1하면서 이동하면된다. 


베이스 케이스는

if(left == 1 && right == n) {

return 0;

}

이렇게 된다. 


그리고 현재 켜져있는 값들을 계산해야된다. 


(a[now]-a[left-1])*(s[n]-s[right]+s[left-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
66
67
68
69
70
71
72
73
74
package Problems;
import java.util.Arrays;
/**
 * 
 * 백준 2315 가로등끄기 
 * 
 *  동적계획
 * 
 *
 */
import java.util.Scanner;
public class Boj2315dp {
    
    public static int n,m;
    public static int a[] = new int[1001];
    public static int w[] = new int[1001];
    public static int s[] = new int[1001];
    public static int d[][][] = new int[1001][1001][2];
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        m= in.nextInt();
        
        for(int i = 1; i <= n; i++) {
            a[i] = in.nextInt();
            w[i] = in.nextInt();
            s[i] = s[i-1+ w[i];
        }
        
        for(int i = 0; i < 1001; i++) {
            for(int j = 0; j < 1001;j++) {
                for (int w = 0; w <2; w++) {
                    d[i][j][w] = -1;
                    
                }
            }
        }
        
        System.out.println(solution(m,m,0));
        
    }
    
    public static int solution(int left, int right, int where) {
        
        if(left == 1 && right == n) {
            return 0;
        }
        
        if(d[left][right][where] != -1) {
            return d[left][right][where];
        }
        
        int ans = 214748364;
        
        int now = where == 0 ? left : right;
        System.out.println("now  :  " + now);
        if(left - 1 >= 1) {
            ans = Math.min(ans, solution(left-1,right,0+ (a[now]-a[left-1])*(s[n]-s[right]+s[left-1]));
        } 
        
        if(right + 1 <=n) {
            ans = Math.min(ans, solution(left,right+1,1+ (a[right+1]-a[now])*(s[n]-s[right]+s[left-1]));
            
        }
        
        d[left][right][where] = ans;
        
        return ans;
    
    
    }
 
}
 
cs

'알고리즘(추가예정) > 동적계획법' 카테고리의 다른 글

[프로그래머스] 네트워크  (0) 2020.08.23
[프로그래머스] 2n 타일링  (0) 2020.08.23
백준 1563 개근상  (0) 2017.11.14
백준 1495 기타리스트  (0) 2017.11.13
백준 11048 이동하기  (0) 2017.11.08

문제보기


실제로 이 문제를 푸는 방법은 여러가지가 있더라 , 

하지만 배열을 다루는 것에 있어 미숙한점을 알고 있기때문에

조건을 배열로 바꾸어 5차원 배열로 풀어보았다. 

 

풀이는 간단하지만 복잡하다. 

경우를 충분히 나누면 풀 수 있다. 

다만 그 경우가 다른 쉬운 다이나믹 문제보다 조건이 많아 처음에는

힘들었다. 


조건의 예를 들어보자 

점화식을 설명해보자면 

D[현재몇일][오늘의 출결][어제의 출결][그제의 출결][지각횟수]

이다. 

오늘 출결했다고 하면 뭘해도 상관없다.  이런식으로 조건을 나열하여 풀면된다. 

처음에는 상당히 시간이 걸렸다.

D[i][0][prev][prev2][0] += D[i-1][prev][prev2][prev3][0];

D[i][0][prev][prev2][1] += D[i-1][prev][prev2][prev3][1];


그리고 안되는 조건을 살펴보자면 

now , prev , prev2가 다 결석이면 안된다. 연속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
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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
package Problems;
 
/**
 * 
 * 
 * 백준 1563 개근상
 * 
 * 동적계획
 *
 */
import java.util.Scanner;
 
public class boj1563dp {
    public static int mod = 1000000;
 
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[][][][][] D = new int[1001][3][3][3][2];
 
        for (int now = 0; now < 3; now++) {
            for (int prev = 0; prev < 3; prev++) {
                for (int prev2 = 0; prev2 < 3; prev2++) {
 
                    // 결석 연속3번은 안
                    if (now == 1 && prev == 1 && prev2 == 1) {
                        continue;
                    }
 
                    // 지각 2번은 안됨
                    if ((now == 2 && prev == 2|| (now == 2 && prev2 == 2|| (prev == 2 && prev2 == 2)) {
                        continue;
                    }
 
                    if (now == 2 || prev == 2 || prev2 == 2) {
                        D[3][now][prev][prev2][1= 1;
                    } else {
 
                        D[3][now][prev][prev2][0= 1;
 
                    }
 
                }
            }
        }
 
        for (int i = 4; i <= n; i++) {
            for (int prev = 0; prev < 3; prev++) {
                for (int prev2 = 0; prev2 < 3; prev2++) {
                    for (int prev3 = 0; prev3 < 3; prev3++) {
 
                        // 출석했을
                        D[i][0][prev][prev2][0+= D[i - 1][prev][prev2][prev3][0];
                        D[i][0][prev][prev2][0] %= mod;
                        D[i][0][prev][prev2][1+= D[i - 1][prev][prev2][prev3][1];
                        D[i][0][prev][prev2][1] %= mod;
 
                        // 결석
 
                        if (prev == 1 && prev2 == 1) {
 
                        } else {
 
                            D[i][1][prev][prev2][0+= D[i - 1][prev][prev2][prev3][0];
                            D[i][1][prev][prev2][0] %= mod;
                            D[i][1][prev][prev2][1+= D[i - 1][prev][prev2][prev3][1];
                            D[i][1][prev][prev2][1] %= mod;
 
                        }
 
                        D[i][2][prev][prev2][1+= D[i - 1][prev][prev2][prev3][0];
                        D[i][2][prev][prev2][1] %= mod;
 
                    }
                }
            }
        }
        
        int ans = 0;
        
        for(int i = 0; i < 3; i++) {
            for(int j = 0; j < 3; j++){
                for(int k = 0; k < 3; k++) {
                    for(int l = 0; l < 2; l++) {
                        ans += D[n][i][j][k][l];
                        ans%=mod;
                    }
                }
            }
        }
        
        System.out.println(ans);
 
    }
 
}
 
cs


'알고리즘(추가예정) > 동적계획법' 카테고리의 다른 글

[프로그래머스] 2n 타일링  (0) 2020.08.23
백준 2315 가로등 끄기  (0) 2017.11.16
백준 1495 기타리스트  (0) 2017.11.13
백준 11048 이동하기  (0) 2017.11.08
백준 1912 연속합  (0) 2017.11.07

문제보기


*경우는 두 가지가 있습니다. (더하기 , 뺴기)

*조건에 따라서 필터링 해줍니다 (0보다 커야됩니다.)

*2차원으로 만들어 값을 체크하면서 진행합니다. 

 -> D[N][M]    

*곡 연주가 가능하다면 배열의 해당칸에 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
package Problems;
 
/**
 * 
 * 백준 1495 dp
 *
 */
import java.util.Scanner;
 
public class Boj1495dp {
 
    public static int n, s, m;
 
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        s = in.nextInt();
        m = in.nextInt();
        int max = -1;
        int[][] arr = new int[n + 1][m + 1];
 
        int[] v = new int[n + 1];
 
        for (int i = 1; i <= n; i++) {
            v[i] = in.nextInt();
        }
        arr[0][s] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                if (arr[i-1][j] == 1) {
                    if (j + v[i] > m && j - v[i] < 0) {
                        continue;
                    }
 
                    if (j + v[i] <= m) {
                        arr[i][j + v[i]] = 1;
                    }
 
                    if (j - v[i] >= 0) {
                        arr[i][j - v[i]] = 1;
 
                    }
 
                }
 
            }
        }
 
        int result = -1;
        for (int j = 0; j <= m; j++) {
            if (arr[n][j] == 1) {
                if (result < j) {
                    result = j;
                }
            }
        }
 
        System.out.println(result);
 
    }
 
}
 
cs


'알고리즘(추가예정) > 동적계획법' 카테고리의 다른 글

백준 2315 가로등 끄기  (0) 2017.11.16
백준 1563 개근상  (0) 2017.11.14
백준 11048 이동하기  (0) 2017.11.08
백준 1912 연속합  (0) 2017.11.07
백준 11055 가장 큰 증가하는 부분수열  (0) 2017.11.07

문제 보기


* 몸이 안좋아서 , 짧게 하겠습니다.


4가지 풀이가 있습니다. 


solve1 은 현재칸을 기준으로 전 단계가 될 수 있는 칸들을 계산합니다.


solve2 는 현재칸을 기준으로 현재칸이 갈 수 있는 3가지의 경로를 계산합니다.


solve3는 solve1을 봤을때 대각선으로 바로 이동하는 수는 다른 방법으로 오는 수들 보다 작을 수 밖에 없습니다. 

이유는 모두 0보다 크기때문입니다. 그러기 때문에 수가 줄어들일이 없습니다. solve1 - 대각선 이라고 생각하시면 될 것 같습니다.


solve4는 재귀로 풀어봤습니다. 딱히 어려운건 없습니다.


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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
package Problems;
 
/**
 * 
 * 
 * 백준 11048 이동하기 
 *  
 *
 */
import java.util.Scanner;
 
public class Boj11048dp {
 
    public static int n, m;
 
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        m = in.nextInt();
 
        int[][] arr = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                arr[i][j] = in.nextInt();
            }
        }
        int[][] solve4 = new int[n + 1][m + 1];
        
        solve1(arr);
        solve2(arr);
        solve3(arr);
        int temp = solve4(arr,solve4,n,m);
        System.out.println(temp);
 
    }
 
    public static void solve1(int[][] arr) {
 
        int[][] dp = new int[n + 1][m + 1];
 
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                dp[i][j] = Math.max(dp[i - 1][j], Math.max(dp[i - 1][j - 1], dp[i][j - 1])) + arr[i][j];
                System.out.println("arr" + arr[i][j] + "    :   dp"  + dp[i][j]);
            }
        }
 
        System.out.println(dp[n][m]);
 
    }
 
    public static void solve2(int[][] arr) {
        int[][] dp = new int[n + 1][m + 1];
 
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
 
                if ( j + 1 <=&& dp[i][j + 1< dp[i][j] + arr[i][j + 1]) {
                    dp[i][j + 1= dp[i][j] + arr[i][j + 1];
                }
 
                if (i + 1 <= n && j + 1 <= m && dp[i + 1][j + 1< dp[i][j] + arr[i + 1][j + 1]) {
                    dp[i+1][j + 1= dp[i][j] + arr[i + 1][j + 1];
                }
 
                if (i + 1 <=&& dp[i + 1][j] < dp[i][j] + arr[i + 1][j]) {
                    dp[i+1][j] = dp[i][j] + arr[i + 1][j];
                }
            }
        }
 
        System.out.println(dp[n][m]);
    }
 
    public static void solve3(int[][] arr) {
 
        int[][] dp = new int[n + 1][m + 1];
 
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + arr[i][j];
            }
        }
 
        System.out.println(dp[n][m]);
 
    }
 
    public static int solve4(int[][] arr, int[][] dp, int x, int y) {
 
        if (x == 1 && y == 1) {
            return arr[1][1];
        }
        if (x < 1 || y < 1) {
            return 0;
        }
 
        if (dp[x][y] > 0) {
            return dp[x][y];
        }
 
        dp[x][y] = solve4(arr, dp, x - 1, y) + arr[x][y];
        int temp = solve4(arr, dp, x, y - 1+ arr[x][y];
 
        if (dp[x][y] < temp) {
 
            dp[x][y] = temp;
        }
 
        return dp[x][y];
 
    }
 
}
 
cs


문제보기 


연속합을 구할때 유의할점은 

음수를 포함해도 답이 될때가 있다는 것이다. 

예를 들어 10 -1 11 일때, 음수를 포함하지 않으면 답이 나오질 않는다. 음수를 포함해서 10 + (-1) + 11 이 되어야만 가장 큰 연속합이된다.


D[i]는 A[i]로 끝나는 최대 연속합을 저장하는 배열이다. 


1. A[i-1]로 끝나는 연속합에 , A[i]가 포함된다. 

2. 1번의 경우보다 A[i]가 큰 경우이다. 


이 두개의 경우로 식을 세우면 된다.


D[i] = Math.max(A[i],D[i-1]+A[i])


시간복잡도는 O(N)이다. N번의 횟수와 계산식2개면 되니까! 


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
package Problems;
/**
 * 
 * 백준 1912 연속합 
 * 
 * 동적 계획
 * 
 */
import java.util.Scanner;
 
public class Boj1912dp {
    
    public static int n,arr[],dp[];
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        arr = new int[n+1];
        dp = new int[n+1];
        
        for(int i = 1; i < n+1; i++) {
            arr[i] = in.nextInt();
        }
        
        for(int i = 1; i < n+1; i++) {
            
            dp[i] = Math.max(arr[i], dp[i-1]+arr[i]);
            
        }
        
        int ans = dp[1];
        
        for(int i = 1; i < n+1; i++) {
            
            if(ans < dp[i]) {
                ans = dp[i];
            }
        }
        
        System.out.println(ans);
        
    }
 
}
 
cs


+ Recent posts