최고의 개발자 (목표)

프로그래머스에서 하루에 level 0 문제를 4개씩 25일간 풀면 머쓱이 스탬프를 준다. (+ 다른 사람의 답을 보면 안된다.)

SSAFY에서 자바로만 코딩테스트 공부를 하다보니, js를 까먹을 것 같아서 하루에 4문제씩 js로 풀었다. 덕분에 깃헙 잔디 심기도 다시 시작했다.

비록 어려운 문제는 아니지만 바쁜 와중에도 꾸준히 풀었다는 것이 뿌듯하다!

앞으로는 level1 문제들을 차근차근 풀어가고 싶다 🙂

문제

https://school.programmers.co.kr/learn/courses/30/lessons/42748

코드

function solution(array, commands) {
    const answer = []; // 결과를 저장할 배열

        // commands 를 돌며 각 경우의 값을 구한다.
    for(let i = 0; i < commands.length; i++){
        const arr = array.slice(commands[i][0]-1, commands[i][1]).sort((a,b)=>a-b);
        answer.push(arr[commands[i][2]-1]);
    }

    return answer;
}

해설

입력으로 들어오는 array를 조건에 맞게 잘라 원하는 인덱스의 값을 반환하는 문제이다.

js의 Array.prototype.slice() 를 이용하면 쉽게 구할 수 있다.

command[i][0]-1은 begin, command[i][1]은 end가 된다. 배열은 0번째 인덱스 부터 시작하지만, 문제에서는 1부터 시작이기 때문에, 배열의 인덱스로 맞추어 주려면 1을 빼주어야한다.

command[i][1]의 경우는 1을 빼주지 않아도 된다. 왜냐하면 slice 함수는 end-1 인덱스 까지 잘라주기 때문이다.

그 후 sort 함수를 이용해서 자른 배열을 정렬시켜주었다. 람다 함수를 이용해서 오름차순 정렬을 해주었는데, 따로 정렬 조건을 부여하지 않으면 원하는 대로 정렬이 되지 않을 수 있다.

js는 오름차순 정렬을 위해 그냥 sort() 만 사용하면 [10,9]를 정렬할 경우 [10,9] 로 정렬이된다. 원하는 결과인 [9,10] 과 다르게 나온다. 그 이유는 처음 앞 숫자인 1과 9를 비교했을 때 9가 크기 때문이다. 따라서 원하는 대로 정렬을 하려면 정렬 조건을 부여해주는 것이 좋다.

정렬이 완료되었다면, command[i][2]번째 인덱스를 구헤야한다. 그러나 위에서 말했듯이, 문제에서는 1부터 시작하지만 배열은 0번째 인덱스부터 시작하므로 우리가 만든 배열에 대입하기 위해서는 1을 빼주어야한다.

* Array.prototype.slice()

배열명.slice([begin[, end]])

배열의 begin 인덱스부터 end-1 인덱스까지 잘라서 반환한다.

const arr = [1,2,3,4,5]

// begin & end를 모두 입력받는 경우
// begin 부터 end-1 인덱스까지 잘라 반환
console.log(arr.slice(1,3)) // [2,3]

// begin 만 입력 받는 경우
// array[begin]부터 array의 끝까지 잘라 반환
console.log(arr.slice(3)) // [3,4,5]

// 아무것도 입력하지 않는 경우
// array 그대로 반환
console.log(arr.slice()) // [1,2,3,4,5]

* Array.prototype.sort()

배열명.sort([compareFunction])

const arr = [8,9,10]

// sort()만 사용하는 경우
console.log(arr.sort()) // [10,8,9]

// 오름차순 정렬
console.log(arr.sort((a,b)=>a-b)) // [8,9,10]

// 내림차순 정렬
console.log(arr.sort((a,b)=>b-a)) // [10,9,8]

문제

Backward numbers are numbers written in ordinary Arabic numerals but the order of the digits is reversed. The first digit becomes the last, and vice versa. For example, the number 1245 becomes 5421. Note that all leading zeroes are omitted. This means that if the number ends with a zero, the zero is lost by the reversal; e.g., 1200 gives 21. Also note that the reversed numbers never have any trailing zeroes.

We need to calculate with backward numbers and your task is to write a program that can add two backward numbers and output their sum as a backward number. Of course, the result is not unique (e.g., 21 could be 12, 120, or 1200 before the reversal). Thus, we assume that no zeroes were lost in the reversal (e.g., we assume that the original number was 12).

입력

The input consists of N cases. The first input line contains only the integer N, and we assume that N > 0. The follow the cases. Each case consists of exactly one line with two non-negative integers separated by a space. These are the reversed numbers you are to add.

We assume that all numbers are in the range 0 ≤ n < 109.

출력

For each case, print exactly one line containing only one integer—the backward sum of the two backward numbers. Omit any leading zeroes in the output.

코드

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuffer sb;

        int N = Integer.parseInt(br.readLine());

        for(int i = 0; i < N; i++){
            String[] arr = br.readLine().split(" ");
            for(int j = 0; j <2; j++){
                sb = new StringBuffer(arr[j]);
                arr[j] = sb.reverse().toString();
            }
            int sum = Integer.parseInt(arr[0]) + Integer.parseInt(arr[1]);
            String sumSt = Integer.toString(sum);
            sb = new StringBuffer(sumSt);
            System.out.println(Integer.parseInt(sb.reverse().toString()));
        }

    }
}

풀이

이 문제는 두 수를 입력받고 각각 reverse 한 뒤 더해서 다시 reverse 한 값을 출력하는 것이다.

예를 들어 예제 입력 1에 있는 24와 1의 경우, 24를 거꾸로 바꿔서 42로, 1을 거꾸로 바꿔서 1로 해놓고 더하면 43이 된다. 그리고 다시 거꾸로 바꾸면 34가 된다. 즉 답은 34가 된다.

또 다른 예시인 794의 경우, 305를 바꾼 503과 794를 바꾼 497을 더해준다. 그럼 1000이 나오고, 1000을 거꾸로 바꾸면 0001이 된다. 이때 숫자의 경우 앞에 있는 0은 생략해주기 때문에 1이 나오게 된다.

숫자를 int로 입력받아서 거꾸로 돌리는 게 복잡할 것 같아 일단 입력을 다 String으로 받고, StringBuffer에 있는 함수인 reverse를 이용해 입력받은 숫자를 거꾸로 돌려주었다. 거꾸로 돌린 숫자들을 Integer.parseInt()로 숫자로 바꾼 후 더해주었고, 그걸 다시 String으로 변환해 reverse함수로 거꾸로 돌려주었다.

앞에 0이 있는 경우를 대비해 출력할 때 int로 형을 변환해서 출력해주었다.

문제

Undercut is a card game where two players each have five cards numbered one through five. At each round, each player selects a card, then simultaneously reveals it. If the cards are of equal value, there is no score. Otherwise, there are two cases: the two cards are exactly one point apart (this is called an undercut), or the cards are more than one point apart. In the latter case, the person revealing the larger of the cards gets the number of points on the larger card. In the case of an undercut the player with the lower card gets the sum of the two cards. The exception to this is when the cards are 1 and 2, in which case the player with the lower card gets 6 points (instead of only 3 points). After each round, the cards are returned to the hands and they play another round.

For example, if there are 5 rounds and player A plays (in this order) 5, 3, 1, 3, 5 and player B plays 3, 3, 3, 3, 4, then the scoring for each round would be: A gets 5 points, no points, B gets 3 points, no points, B gets 9 points. The totals would be A: 5, B: 12.

In this problem you will be given card plays for both players and must determine the final scores.

입력

There will be multiple input instances. Each instance will be one game. The first line of input for a game will be an integer n <= 20. (A value of n = 0 terminates input.) The next two lines will each contain n integers between 1 and 5 inclusive indicating the cards played on each of n rounds. The first line are player A's card plays and the second line are player B's card plays.

출력

Each input instance should generate one line of output of the form:

A has a points. B has b points.

where the value of a and b are for you to determine. A blank line should separate output lines.

코드

import sys

if __name__ == '__main__':

    while True:
        plays = int(sys.stdin.readline().rstrip())
        
        if plays==0:
            break

        A_point = 0
        B_point = 0

        A = list(map(int, sys.stdin.readline().rstrip().split(" ")))
        B = list(map(int, sys.stdin.readline().rstrip().split(" ")))

        for i in range(plays):
            # 한 개 차이면 적은 수를 가진 애가 이김
            # 자신의 카드 넘버와 상대의 카드 넘버 만큼
            if abs(A[i]-B[i]) == 1:
                if A[i] > B[i]:
                    if A[i] == 2:
                        B_point += 6
                    else:
                        B_point += A[i] + B[i]
                else:   # B[i] > A[i]
                    if B[i] == 2:
                        A_point += 6
                    else:
                        A_point += A[i] + B[i]
            elif A[i] < B[i]:
                B_point += B[i]
            elif A[i] > B[i]:
                A_point += A[i]

        print("A has {} points. B has {} points.\n".format(A_point, B_point))

풀이

문제를 먼저 해석해보자면, A와 B가 카드게임을 하는데 이때 이기는 조건이 여러 가지이다.

① 두 카드의 숫자 차이가 1보다 클 경우, 숫자가 큰 카드를 가진 사람이 이긴다. 이때, 얻는 점수는 자신의 카드 숫자만큼이다.(큰 카드)

② 두 카드의 숫자 차이가 1일 경우, 숫자가 작은 카드를 가진 사람이 이긴다. 이때, 얻는 점수는 자신의 카드와 상대방의 카드 숫자를 더한 값이다.

③ ②번의 예외로, 두 카드가 1과 2일 경우, 무조건 낮은 카드를 가진 사람이 6점을 얻는다.

④ 두 카드의 숫자가 같을 경우, 무승부로 아무도 점수를 얻지 않는다.

위 조건에 맞춰 풀면 된다. 입력을 0이 나올 때까지 받기 때문에 무한 반복을 하고 0이 나오면 break 할 수 있도록 코드를 작성했다. 첫 번째 if 문에서는 A와 B의 카드 차가 1인지 확인했다. 이때 어느 수가 더 큰지 모르기 때문에 abs() 함수를 이용해 절댓값을 씌워서 1인지 확인했다. 그 후, 두 개의 카드가 각각 1과 2라면 6점을 더해주었다. 이때 이미 if 문에서 카드의 차이가 1인지를 확인했기 때문에 A가 B보다 큰 경우, A가 2인지만 확인해주면 B는 자동으로 1이 되므로 A만 조건식에 써주었다. 두 개의 카드가 1과 2가 아니라면 조건 ②에 따라서 두 카드의 합을 점수에 더해주었다.

두 번째와 세 번째 if문의 경우는 조건 ①에 따른 식으로 큰 카드의 수를 점수에 더해주었다.

문제

n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.

예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.

입력

첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

출력

첫째 줄에 답을 출력한다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        String[] st = br.readLine().split(" ");

        int[] dp = new int[n];

        dp[0] = Integer.parseInt(st[0]); 
        int max = dp[0];

        for(int i = 1; i < n; i++){
            dp[i] = Math.max(dp[i-1]+Integer.parseInt(st[i]), Integer.parseInt(st[i]));
            max = max < dp[i] ? dp[i] : max;
        }

        System.out.println(max);

    }
}

풀이

dp[i]는 i번째 정수까지 있을 때의 구할 수 있는 합 중 가장 큰 합이다.

st는 입력받은 배열이다.

이때 정수 n이 최소 1개이므로 dp[0]에는 st[0]을 미리 넣고, 가장 큰 합을 저장하는 변수인 max에도 st[0]을 넣어놓는다.

dp[i]는 i-1번째 정수까지 있을 때의 구할 수 있는 최대 합에 st[i]를 더한 것이 될 수도 있고, 아니면 현재 들어온 st[i] 자체가 될 수도 있다. 따라서 두 수를 비교해 더 큰 수를 dp[i]에 저장하고, max 값도 비교해서 바꿔준다.

문제

Mahima has been experimenting with a new style of art. She stands in front of a canvas and, using her brush, flicks drops of paint onto the canvas. When she thinks she has created a masterpiece, she uses her 3D printer to print a frame to surround the canvas.

Your job is to help Mahima by determining the coordinates of the smallest possible rectangular frame such that each drop of paint lies inside the frame. Points on the frame are not considered inside the frame.

입력

The first line of input contains the number of drops of paint, N, where 2 ≤ N ≤ 100 and N is an integer. Each of the next N lines contain exactly two positive integers X and Y separated by one comma (no spaces). Each of these pairs of integers represents the coordinates of a drop of paint on the canvas. Assume that X < 100 and Y < 100, and that there will be at least two distinct points. The coordinates (0, 0) represent the bottom-left corner of the canvas.

출력

Output two lines. Each line must contain exactly two non-negative integers separated by a single comma (no spaces). The first line represents the coordinates of the bottom-left corner of the rectangular frame. The second line represents the coordinates of the top-right corner of the rectangular frame.

코드

import sys

if __name__ == '__main__':
    N = int(sys.stdin.readline().rstrip())

    x_coordinates = []
    y_coordinates = []

    for i in range(N):
        x,y = map(int, sys.stdin.readline().rstrip().split(","))
        x_coordinates.append(x)
        y_coordinates.append(y)
    
    print(min(x_coordinates)-1,min(y_coordinates)-1, sep=",")
    print(max(x_coordinates)+1,max(y_coordinates)+1, sep=",")

풀이

각 점을 포함하는 프레임의 왼쪽 아래와 오른쪽 위 좌표를 구하는 것이므로, 왼쪽 아래와 오른쪽 위 프레임의 위치가 어디가 될지 생각해보면 된다. 프레임의 왼쪽 아래의 x, y 좌표는 분포하는 점 중에서 가장 작은 x와 가장 작은 y와 같을 것이다. 이때, 프레임이 점 밖에 있어야 하기 때문에, (가장 작은 x-1, 가장 작은 y-1)이 왼쪽 아래의 좌표가 된다.

오른쪽 위는 위가 같은 방법으로 (가장 큰 x+1, 가장 작은 y+1) 가 될 것이다.

문제

Now that Snapchat and Slingshot are soooo 2018, the teenagers of the world have all switched to the new hot app called BAPC (Bidirectional and Private Communication). This app has some stricter social rules than previous iterations. For example, if someone says goodbye using Later!, the other person is expected to reply with Alligator!. You can not keep track of all these social conventions and decide to automate any necessary responses, starting with the most important one: the greetings. When your conversational partner opens with he...ey, you have to respond with hee...eey as well, but using twice as many e’s!

Given a string of the form he...ey of length at most 1000, print the greeting you will respond with, containing twice as many e’s.

입력

• The input consists of one line containing a single string s as specified, of length at least 3 and at most 1000.

출력

Output the required response.

코드

import java.util.Scanner;

public class 백준_17548 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String st = sc.next();

        int eCount = 0;
        
        for(int i = 0; i < st.length(); i++){
            char c = st.charAt(i);
            if(c == 'e'){
                eCount += 1;
            }
        }
        System.out.print("h");
        for(int i = 0; i < eCount*2; i++){
            System.out.print("e");
        }
        System.out.print("y");
    }
}

풀이

문제를 해석해보면 입력 String의 e를 2배로 출력하면 된다. 최소 입력은 'hey'이다.

입력받은 String에서 e의 개수를 세서 eCount 변수에 저장했다. 

출력은 h, e, y를 따로 출력해 e를 중간에 여러 개 출력할 수 있도록 했다.

문제

두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다. 이런 공배수 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 6과 15의 공배수는 30, 60, 90등이 있으며, 최소 공배수는 30이다.

두 자연수 A와 B가 주어졌을 때, A와 B의 최소공배수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000)가 주어진다. 둘째 줄부터 T개의 줄에 걸쳐서 A와 B가 주어진다. (1 ≤ A, B ≤ 45,000)

출력

첫째 줄부터 T개의 줄에 A와 B의 최소공배수를 입력받은 순서대로 한 줄에 하나씩 출력한다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        /* 유클리드 호제법
        1. a와 b의 최대공약수
        == b와 r의 최대공약수
        == r과 r2의 최대공약수
        ...
        a % b => r
        b % r => r2
        r % r2 => r3
        if) r3가 0, 즉 나머지가 0이면 최대공약수는 r2

        2. a와 b의 최대공배수
        -> a*b / gcd(a,b)
        */

        int T = Integer.parseInt(st.nextToken());

        for(int i = 0; i < T; i++){
            st = new StringTokenizer(br.readLine());
            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());

            int r = gcd(A, B);
            System.out.println(A*B/r);

        }
    }

    public static int gcd(int a, int b){
        while(b!=0){
            int r = a % b;
            a = b;
            b = r;
        }
        return a;
    }
}

풀이

이 문제는 시간제한이 1초이기 때문에 유클리드 호제법을 써야 한다.

유클리드 호제법을 이용해 최대공약수를 구하고, A * B / 최대공약수를 해서 최소공배수를 구했다.

유클리드 호제법은 https://chelim.tistory.com/49 에 따로 설명을 올렸다.

최대공약수란?

A와 B의 공약수 중 가장 큰 수이다. 여기서 공약수란 A의 약수와 B의 약수 중 겹치는 수이다.

예를 들어, 6과 24를 보면 6의 약수는 1,2,3,6이고 24의 약수는 1,2,3,4,6,8,12,24 이다.

즉 공약수는 1,2,3,6이다. 여기서 가장 큰 6이 6과 24의 최대공약수가 된다.

이떄, 24를 6으로 나누면 나머지가 0이다. 

A와 B의 최대공약수를 구하려고 할 떄, A % B = 0 이라면 B가 A, B의 최대공약수가 된다.

유클리드 호제법이란?

자연수 A, B의 최대공약수를 구하는 알고리즘이다.

A % B = R이라고 해보자. 만약 이때 R이 0이라면 B가 최대공약수일 것이다. 0이 아니라면

B % R = R2라고 해보자. 만약 이때 R2가 0이라면 R이 최대공약수일 것이다. 0이 아니라면

R % R2 = R3라고 해보자. 앞 과정을 나머지가 0이 될 때까지 계속 반복해서 최대공약수를 구한다.

예를 들어, 48과 36의 최대공약수를 유클리드 호제법을 이용해서 구해보자.

48 % 36 = 12. 나머지가 0이 아니므로 36과 12의 나머지를 구한다.

36 % 12 = 0. 나머지가 0이다. 즉 48과 36의 최대공약수는 12가 된다.

예를 들어, 16과 10의 최대공약수를 유클리드 호제법을 이용해서 구해보자.

16 % 10 = 6이다. 나머지가 0이 아니므로 10과 6의 나머지를 구한다.

10 % 6 = 4. 나머지가 0이 아니므로 6과 4의 나머지를 구한다.

6 % 4 = 2. 나머지가 0이 아니므로 4와 2의 나머지를 구한다.

4 % 2 = 0. 나머지가 0이다. 2가 최대공약수가 된다.

위의 알고리즘을 코드로 바꿔보자.

public static int gcd(int a, int b){
        while(b!=0){
            int r = a % b;
            a = b;
            b = r;
        }
        return a;
    }

앞에서는 a와 b를 나누고, b와 r을 나누고, r과 r2를 나눴다. 즉 a와 b를 나눈 나머지인 r을 구하고 a 자리에 b를, b 자리에 r을 넣어서 다음에는 b % r이 될 수 있도록 한다. while문에서 b가 0인지 0이 아닌지 확인하는 이유도 while문 안에서 조건을 확인하기 전, b자리에 r을 넣었기 때문이다. 만약 b가 0이라면(나머지가 0), a에 b가, b에는 r이 들어있는 상황이기 때문에 원래대로라면 b를 출력해야 맞지만, 현재 b의 값을 가지고 있는 a를 출력해야한다.

최소공배수란?

A와 B의 공배수 중 가장 작은 수이다. 여기서 공배수란 A의 배수와 B의 배수 중 겹치는 수이다.

예를 들어, 48과 36를 보면 48의 배수는 48, 96, 144, 192, 240..이고 36의 배수는 36, 72, 108, 144, .. 이다.

즉 최소공배수는 144이다.

최대공약수와 최소공배수와의 관계

유클리드 호제법에 쓰였던 예시인 48, 36으로 최대공약수와 최소공배수의 관계를 생각해보자.

48과 36의 최소공배수는 144이고, 최대공약수는 12이다.

그럼 144가 48과 36의 최대공약수인 12와 어떤 관계가 있을까?

12는 최대공약수이기 때문에 48과 36의 약수 중 하나이다. 즉 12에 어떤 수를 곱하면 48이 나오고, 12에 어떤 수를 곱하면 36이 나온다. 이때 12 * x = 48, 12 * y = 36이라고 생각해보면, x와 y는 서로소이며 x * y  = 최대공약수이다.

또한 48 * 36 = 12 * 12 * x * y 이다. 이때 양변에 최대공약수를 나눠주면, (48 * 36) / 12 = 12 * 12 이고 , 12 * 12는 144 즉 최소공배수이다. 따라서 A * B / 최대공약수 = 최소공배수 이다. 

위의 유클리드 호제법으로 최대공약수를 먼저 구한뒤, 구한 최대공약수를 이용해 최소공배수를 구할 수 있다.

문제

계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다.

예를 들어 <그림 2>와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총점수는 10 + 20 + 25 + 20 = 75점이 된다.

계단 오르는 데는 다음과 같은 규칙이 있다.

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
3. 마지막 도착 계단은 반드시 밟아야 한다.

따라서 첫 번째 계단을 밟고 이어 두 번째 계단이나, 세 번째 계단으로 오를 수 있다. 하지만, 첫 번째 계단을 밟고 이어 네 번째 계단으로 올라가거나, 첫 번째, 두 번째, 세 번째 계단을 연속해서 모두 밟을 수는 없다.

각 계단에 쓰여 있는 점수가 주어질 때 이 게임에서 얻을 수 있는 총 점수의 최댓값을 구하는 프로그램을 작성하시오.

입력

입력의 첫째 줄에 계단의 개수가 주어진다.

둘째 줄부터 한 줄에 하나씩 제일 아래에 놓인 계단부터 순서대로 각 계단에 쓰여 있는 점수가 주어진다. 계단의 개수는 300 이하의 자연수이고, 계단에 쓰여 있는 점수는 10,000 이하의 자연수이다.

출력

첫째 줄에 계단 오르기 게임에서 얻을 수 있는 총 점수의 최댓값을 출력한다.

코드

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int[] stairs = new int[N+2];
        int[] dp = new int[N+2]; // 계단 1칸이면 밑에 0,1,2 값에서 outofindex

        for(int i = 0; i < N; i++){
            stairs[i] = Integer.parseInt(br.readLine());
        }

        // dp[0] 즉 한 칸 이동에서의 최대는 자기 자신
        dp[0] = stairs[0];
        // dp[1] 은 자기자신과 전칸+자기자신 중 최대
        dp[1] = Math.max(stairs[0]+stairs[1], stairs[1]);
        // dp[2] 는 st[0]+st[2] 또는 st[1]+st[2] 중 최대
        dp[2] =  Math.max(stairs[0]+stairs[2], stairs[1]+stairs[2]);

        for(int i = 3; i < N; i++){
            dp[i] = Math.max(dp[i-3] + stairs[i-1] + stairs[i], dp[i-2] + stairs[i]);
        }
        System.out.println(dp[N-1]);
    }   
}

풀이

문제의 조건을 보고 dp 식을 세워야 한다. 마지막 계단은 무조건 밟아야 한다는 것과, 1칸이나 2칸 이동이 가능하지만 1칸 이동을 연속으로 3번은 불가능하다는 것이다. 즉 1번 계단->2번 계단으로 이동했다면 2번 계단에서는 무조건 4번 계단으로 가는 선택지 밖에 존재하지 않는다.

일단 마지막 계단을 무조건 밟아야 한다는 조건을 생각해보자. 마지막 계단을 n번째 계단이라고 가정하면, n-1번째 계단을 밟고 마지막 계단을 밟는 것과 n-2번째 계단을 밟고 마지막 계단을 밟는 경우가 존재한다. 

이때, n-1번째 계단에서 n번째 계단으로 가는 경우는 더 생각해봐야 하는 것이 있다. n-2번째 -> n-1번째 -> n번째는 조건에 어긋나기 때문에 n-1번째 -> n번째로 가기 위해서는 무조건 n-3번째 -> n-1번째 -> n번째가 되어야한다. 따라서

아래 그림과 같이 최종적으로 2가지 방법을 비교해 총 점수가 더 큰 계단으로 이동해야 한다.

이를 식으로 바꾸면, 왼쪽의 경우는 dp[n-3] + stairs[n-1] + stairs[n] 이 되고, 오른쪽의 경우는 dp[n-2] + stairs[n] 이 된다.

따라서, dp[n] = max(dp[n-3] + stairs[n-1] + stairs[n], dp[n-2] + stairs[n]) 로 구할 수 있다.

dp[0], dp[1], dp[2]는 조건식이 달라서 for문에 들어가기전에 따로 값을 넣어줬고, 계단이 1칸일 때 dp[1], dp[2]에 값을 넣어주는 라인에서 ArrayOutOfIndex 에러가 나기 때문에 dp와 stairs의 크기를 N+2로 지정했다.