Social Developer
Home
  • 분류 전체보기 (121)
    • Life (3)
    • Idea note (0)
    • Algorithms (84)
    • CS (16)
      • Data Structure (7)
      • Network (9)
    • Skill (13)
      • Spring (0)
      • Java (9)
      • Infra (3)
      • Etc. (1)
Home
  • 분류 전체보기 (121)
    • Life (3)
    • Idea note (0)
    • Algorithms (84)
    • CS (16)
      • Data Structure (7)
      • Network (9)
    • Skill (13)
      • Spring (0)
      • Java (9)
      • Infra (3)
      • Etc. (1)
블로그 내 검색

Social Developer

어제보다 한 걸음 더

  • Algorithms

    [백준 알고리즘] (DP) 2156번 Java 풀이

    2020. 3. 23.

    by. SDev

    728x90

    DP - 1463, 11726, 11727, 9095, 10844, 11057, 2193, 9465, 2156, 11053, 11055, 11722, 11054, 1912, 2579, 1699, 2133, 9461, 2225, 2011, 11052

    출처: https://plzrun.tistory.com/entry/알고리즘-문제풀이PS-시작하기 [plzrun's algorithm]

     

    알고리즘 문제풀이(PS) 시작하기

    이런건 고수들이나 써야 하지 않나 싶지만, 그래도 1년정도 공부하면서 이 분야를 어떻게 시작해야 할지 써보려 한다. 라고 운을 뗀다음 열심히 내 얘기만 했던 후속편이다. 내 인생사가 궁금하신 분들은 이 글의..

    plzrun.tistory.com

     

     

    백준 알고리즘 2156번

     

     

    hange Nxxxx -> Main && remove package lines!!!

    이클립스에서 작성하면서 문제 이름으로 클래스를 생성하여 풀었기 때문에

    클래스 이름을 Main으로 바꾸고, package 부분도 지우고 제출해야 정상적으로 돌아갑니다.

     

     

    <풀이> - Bottom up

    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
    package dp;
     
    import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
     
    public class N2156 {
     
        static int dp[];
        static int array[];
        public static void main(String[] args) throws NumberFormatException, IOException {
     
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            int n = Integer.parseInt(br.readLine());
            
            dp = new int[n];
            array= new int[n];
            for(int i=0; i<n; i++) {
                array[i] = Integer.parseInt(br.readLine());
            }
            br.close();
            
            System.out.println(calculate(n));
        }
        
        public static int calculate(int n) {
            if(n==1) {
                return array[0];
            }else if(n==2) {
                return array[0]+array[1];
            }else {
                dp[0] = array[0];
                dp[1] = dp[0]+array[1];
                dp[2] = Math.max(dp[1], Math.max(array[0]+ array[2], array[1]+array[2]));
                
                for(int i=3; i<n; i++) {
                    dp[i] = Math.max(dp[i-3]+array[i]+array[i-1], dp[i-2]+array[i]);
                    dp[i] = Math.max(dp[i-1], dp[i]);
                }
                return dp[n-1];
            }
            
        }
     
    }
     
    Colored by Color Scripter
     

     

     

    처음 점화식을 세우는 과정에서 스스로 구하지 못해서 다른 분의 풀이를 참고했다.

    https://hees-dev.tistory.com/30

     

    [BOJ] 백준 2156 포도주시식-java

    문제 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다...

    hees-dev.tistory.com

     

    연속으로 3개를 마시지 못한다고 하는 제약을 3개만 놓고 볼 것이 아니라, 그 이전까지 고려해야한다.

    n번째 포도주를 마신다면,

    1) n-2번째를 마시지 않고, n-1번째를 마신 경우
    -> n-2번째에서 마시지 않았기때문에 n-3번째는 마셔도 되고 안마셔도 된다.
    -> 따라서 dp[n] = dp[n-3] + array[n-1] + array[n]

    2) n-2번째를 마시고, n-1번째를 마시지 않은 경우
    ->n-1번째에서 마시지 않았기때문에 n-2번째는 마셔도 되고 안마셔도 된다.
    -> 따라서 dp[n] = dp[n-2]+array[n]

    두 경우를 비교하여 더 큰 값을 저장하면 된다.

     

    이에 더불어 2번 연속으로 포도주를 마시지 않는 경우도 고려해야한다.

    dp[n], dp[n-1]을 비교해서 더 큰 값을 저장!!

    해주지 않으면 n이 증가한다고해도 dp값이 증가하지 않는 사례가 존재한다.

     

    Github: https://github.com/jaeuk9407/AlgorithmBOJ

     

    jaeuk9407/AlgorithmBOJ

    BaekJoon Online Judge Problems. Contribute to jaeuk9407/AlgorithmBOJ development by creating an account on GitHub.

    github.com

     

    저작자표시 (새창열림)

    'Algorithms' 카테고리의 다른 글

    [백준 알고리즘] (DP) 11055번 Java풀이  (0) 2020.03.27
    [백준 알고리즘] (DP) 11053번 Java 풀이  (0) 2020.03.26
    [백준 알고리즘] (DP) 9465번 Java 풀이  (0) 2020.03.20
    [백준 알고리즘] (DP) 2193번 Java 풀이  (0) 2020.03.16
    [백준 알고리즘] (DP) 11057번 Java 풀이  (0) 2020.03.15

    댓글

    관련글

    • [백준 알고리즘] (DP) 11055번 Java풀이 2020.03.27
    • [백준 알고리즘] (DP) 11053번 Java 풀이 2020.03.26
    • [백준 알고리즘] (DP) 9465번 Java 풀이 2020.03.20
    • [백준 알고리즘] (DP) 2193번 Java 풀이 2020.03.16
    맨 위로
전체 글 보기
  • 인정님 블로그
  • 성현님 블로그
Tistory 로그인
Tistory 로그아웃
로그아웃 글쓰기 관리

Today

Total

Powered by ⓒ Kakao Corp.

Designed by Nana
블로그 이미지
SDev

티스토리툴바