소소한 개발일지

문제

정수 n과 k 그리고 정수배열 n의 길이의 speed와 efficiency가 주어졌습니다. 1부터 n까지 n명의 엔지니어가 있으며 speed[i]와 efficiency[i]는 i번째 엔지니어의 속도와 효율을 의미합니다.

최대 k명의 다른 엔지니어를 n명 중에 선택하여 최대 performance를 낼 수 있는 팀을 만드세요.

팀의 performance는 엔지니어들의 speed를 더한 값에 선택한 엔지니어들 중 최소 efficiency를 곱한 값 입니다.

팀의 최대 performance를 반환하세요. 답이 큰 수일 수 있으니, 답에 modulo \(10^9 + 7\) 연산 후 반환하세요.

예시

Input: n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 2
Output: 60
최대 performance를 낼 수 있는 팀은 엔지니어 2(speed=10 and efficiency=4)와 엔지니어 5(speed=5 and efficiency=7)를 선택하는 것 입니다.
performance는 (10 + 5) * min(4, 7) = 15 * 4 = 60 입니다.

Input: n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 3
Output: 68
위의 예제와 같은 조건이지만 k = 3입니다.
최대 performance를 낼 수 있는 팀은 엔지니어 1과, 엔지니어 2, 그리고 엔지니어 5를 선택하는 것 입니다.
performance = (2 + 10 + 5) * min(5, 4, 7) = 17 * 4 = 68.

Input: n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 4
Output: 72

제약조건

1 <= k <= n <= 105
speed.length == n
efficiency.length == n
1 <= speed[i] <= 10^5
1 <= efficiency[i] <= 10^8

풀이 : Greedy

문제를 쉽게 보고 풀다가 나중에 잘 못 이해한 부분이 있는 것을 확인했습니다 . 이런식의 문제는 처음 풀어보기도 했습니다..

쉽게 오해할 수 있는 부분을 짚고 풀이방식을 설명하며 진행하겠습니다.

최대 k명의 엔지니어를 선택

최대 k명이라는 뜻은 선택된 엔지니어의 수가 k 보다 작을수도 있는 것 입니다.

예를 들어, 엔지니어 1(speed = 10, efficiency = 10)과 엔지니어 2(speed = 1, efficiency = 1)가 있고 k = 2라고 가정합시다.

엔지니어 1 만 고른다면 performance는 100이고 (10 * 10) 엔지니어 2 도 같이 고른다면 11 (11 * 1)입니다.

그렇기에 k명을 넣어서 performance를 계산하는 DFS는 잘못된 접근 이었습니다.

자, 그럼 위의 내용을 고려하며 풀이를 진행하겠습니다.

1. efficiency 기준으로 정렬하기

performance는 선택된 엔지니어 중 최소 efficiency를 곱해줘야 합니다.즉, efficiency가 높을 수록 performance가 커질 확률이 커집니다. 그렇기에 높은 efficiency를 앞으로 올 수 있게 정렬을 합니다.

2. speed에 대해 min heap을 사용하기

priority queue를 사용하여 선택된 엔지니어의 speed를 저장합니다. min heap이기에 제일 위에는 제일 작은 speed가 들어있습니다.

speed는 크면 클 수록 좋기에 k가 넘어가 제거를 할 경우 제일 작은 speed를 빼야합니다.

efficiency로 정렬된 엔지니어를 돌아가며 최대 k명의 엔지니어들을 선택하고 speed를 더해줍니다. 그 후 현재까지 performance와 현재 efficiency에 더해준 speed를 곱한 값과 비교합니다. efficiency가 큰 값부터 작은 값 순으로 들어 있으니 현재 efficiency 값이 최소 efficiency 입니다.

만약 k명이 넘어갈 경우 더해준 speed에서 제일 작은 speed를 빼는데 해당 값은 min heap 제일 위에 저장이 되어 있습니다.

또한, k보다 적게 엔지니어를 선택할 수도 있는데, 이럴경우는 절대적으로 efficiency가 제일 큰 엔지니어들로 구성되지 않으면 성립하지 않습니다. 이 부분이 이해가 애매했었는데 엔지니어 1(speed = 10, efficiency = 10)과 엔지니어 2(speed = 200, efficiency = 1)가 있고 k = 2 일 때 각각 한 명을 고를 경우 performance는 100과 200 입니다.

하지만 둘 다 고를 경우, 1 * 210 = 210 으로 k 이하로 구성할 때 효율이 제일 좋은 엔지니어를 빼면 안된다는 것을 알 수 있습니다.

검증해서 적어보고 싶은데 기회가 생긴다면 진행해보겠습니다.

그리고 모든 경우의 수를 진행한다면 time out이 나게됩니다...

코드는 아래와 같습니다.

class Solution {
    public int maxPerformance(int n, int[] speed, int[] efficiency, int k) {
        int[][] engineers = new int[n][2];
        for (int i = 0; i < n; i++)
            engineers[i] = new int[] {efficiency[i], speed[i]};
        Arrays.sort(engineers, (a, b) -> Integer.compare(b[0], a[0]));

        long speedSum = 0;
        long answer = 0;
        PriorityQueue<Integer> speedMinHeap = new PriorityQueue<>();
        for (int[] engineer : engineers) {
            int currEfficiency = engineer[0];
            int currSpeed = engineer[1];

            if (speedMinHeap.size() >= k)
                speedSum -= speedMinHeap.poll();
            speedMinHeap.add(currSpeed);
            speedSum += currSpeed;
            
            answer = Math.max(answer, speedSum * currEfficiency);
        }

        return (int)(answer % 1000000007);
    }
}

저에게는 hard 다운 문제였습니다.

은근히 DFS나 DP는 조건만 잘걸면 쉽게 풀 수 있는 것 같은데 Greedy는 이해하기 어려울 때가 많은 것 같습니다.

의견 및 질문은 늘 환영합니다 :)

문제

문자열 s와 integer k가 주어졌습니다. s에서 첫 k개의 문자들 중 하나를 선택해 문자열의 끝으로 보낼 수 있습니다.

위의 방법을 몇 번이든 적용해서 만들 수 있는 문자열 중 사전순으로 제일 작은 문자열을 반환해주세요.

예시

Input: s = "cba", k = 1
Output: "acb"
1번째 이동, 'c'를 끝으로 보내 "bac"를 만든다. ("cba -> bac")
2번째 이동, 'b'를 끝으로 보내 "acb"를 만든다. ("bac -> acb")

Input: s = "baaca", k = 3
Output: "aaabc"
1번째 이동, 첫번째 문자인 'b'를 끝으로 보내 "aacab"를 만든다. ("baaca" -> "aacab")
2번째 이동, 세번째 문자인 'c'를 끝으로 보내 "aaabc"를 만든다. ("aacab" -> "aaabc")

제약조건

1 <= k <= s.length <= 1000
s는 영어 소문자로 이뤄져있습니다.

풀이 : 구현

문제를 이해하는데 헷갈려서 시간이 좀 걸렸습니다. 하지만 문제풀이 자체는 간단했습니다.

아마 이런식으로 풀게 하려던 것 같지는 않은데 풀이방식은 아래와 같습니다.

1. k > 2, 문자열 정렬 후 제일 작은 문자열을 반환하기

뒤로 보낼 수 있는 문자가 2개 이상이라면 시간은 걸려도 문자열로 모든 순열을 만들 수 있습니다.

즉, 문자열을 문자 배열로 만들어 정렬해서 반환하면 됩니다.

2. k == 1, 후보 순열의 대소비교 후 제일 작은 문자열을 반환하기

뒤로 보낼 수 있는 문자가 1개 라면 만들 수 있는 순열의 개수는 정해져 있습니다.

문자열의 길이가 n이라면 n번 만큼 첫 글자를 맨 뒤로 넣을 수 있으므로 n번의 대소비교만 진행하면 됩니다.

즉, 가능한 모든 순열을 비교해 최소의 문자열을 반환하면 됩니다.

코드는 아래와 같습니다.

class Solution {
    public String orderlyQueue(String s, int k) {
        if (k > 1) {
            char ch[] = s.toCharArray();
            Arrays.sort(ch);
            return new String(ch);
        }
        else {
            String minStr = new String(s);

            for (int i = 0; i < s.length(); i++) {
                s = s.substring(1) + s.substring(0, 1);
                
                if (minStr.compareTo(s) > 0) {
                    minStr = s;
                }
            }
            
            return minStr;
        }
    }
}

성능향상을 위해 문자열 연산이 많기에 불변객체인 String 대신 가변객체인 StringBuilder로 바꿨습니다.

코드는 아래와 같습니다.

class Solution {
    public String orderlyQueue(String s, int k) {
        if (k > 1) {
            char ch[] = s.toCharArray();
            Arrays.sort(ch);
            return new String(ch);
        }
        else {
            String minStr = new String(s);
            StringBuilder sb = new StringBuilder(s);

            for (int i = 0; i < s.length(); i++) {
                char firstChar = sb.charAt(0);
                sb.deleteCharAt(0);
                sb.append(firstChar);
                
                String rotatedStr = sb.toString();
                if (minStr.compareTo(rotatedStr) > 0) {
                    minStr = rotatedStr;
                }
            }
            
            return minStr;
        }
    }
}

hard라고 하기엔 묘한 문제였습니다.

자주 나올 것 같은 유형은 아니고 "이런 것도 있구나..." 하고 넘어가면 좋을 것 같습니다.

의견 및 질문은 늘 환영합니다 :)

문제

도시의 스카이라인은 멀리서 봤을 때 도시의 건물들로 인해 만들어진 실루엣의 외곽선을 뜻한다.

건물들의 위치와 높이가 주어졌을 때, 이 건물들로 만들어진 스카이라인을 집합해서 반환하면 된다.

건물의 기하학적 정보가 buildings 라는 배열로 주어진다, buildings[i] = [lefti, righti, heighti]

• lefti는 i번째 건물의 왼쪽 끝 좌표이다.
• righti는 i번째 건물의 오른쪽 끝 좌표이다.
• heighti는 i번째 건물의 높이이다.

모든 건물들이 완전히 평평한 표면에서 (높이 : 0) 세워진 완벽한 직사각형 이라고 가정해도 됩니다.

스카이라인은 "key points"로 이뤄진 list로 표현되어야 하고 x좌표로 정렬되어야 합고 다음과 같은 형태여야 합니다.

[[x1, y1], [x2, y2], ...]

각 key point는 스카이라인 왼쪽 부분이고, list의 마지막 point만 늘 y좌표가 0이며 skyline의 끝인 건물들의 오른쪽 끝 부분을 의미합니다.

왼쪽 끝과 오른쪽 끝 사이의 건물들 사이 땅만 있더라도 스카이라인의 외곽선에 포함되어야 합니다.

참고 : 스카이라인 출력에 같은 높이가 연속적으로 나오면 안됩니다. 예를 들어, [..., [2 3], [4 5], [7 5], [11 5], [12 7], ...] 이 되면 안됩니다. 중간에 높이가 5인 부분들이 하나로 합쳐져, [..., [2 3], [4 5], [12 7], ...] 로 반환되어야 합니다.

예시

Input: buildings = [[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]]
Output: [[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]]
A는 input인 건물들이다.
B는 건물들로 만들어진 스카이라인 이다. 빨간 점들이 output으로 출력되는 key point들 이다.

Input: buildings = [[0,2,3],[2,5,3]]
Output: [[0,3],[5,0]]

제약조건

1 <= buildings.length <= 104
0 <= lefti < righti <= 2^^31 - 1
1 <= heighti <= 2^^31 - 1
buildings는 lefti를 기준으로 오름차순으로 정렬되어 있습니다.

풀이 : 구현

간만에 풀어 본 hard 난이도 문제였습니다. 문제를 읽고 hard 난이도가 맞나 생각했지만 난이도 답게 그리 쉽지는 않았습니다.

초반에 떠오른 풀이는 아래와 같습니다.

스카이라인의 왼쪽 끝에서 오른쪽 끝까지의 높이를 계산하고 연속적인 값은 제외하기

input을 모두 돌려가며 left부터 right까지 height의 값을 넣으려고 했습니다.

만약 해당 건물에 값이 있다면 제일 높은 height 값을 유지하려고 했습니다.

하지만 제약조건을 보니 건물의 위치가 int의 범위라 비효율 적이라 생각했습니다. 기각!

아무리 생각해도 확고한 답이 나오지 않아 자료들을 참고했습니다...

결론은 input으로 들어온 각 건물들의 left, right 좌표에 대해 height을 확인하는 방법입니다.

스카이라인의 외곽선은 건물들의 왼쪽 끝과 오른쪽 끝으로만 구성되어 있습니다.

1. 각 건물의 좌표를 위치와 높이 기준으로 정렬하기

우선적으로 각 건물의 양 끝점을 위치와 높이로 저장했습니다.

정렬 기준은 위치가 작을수록 (왼쪽 일수록) 앞으로 정렬하되, 같은 위치라면 더 높은 높이가 앞으로 정렬되었습니다.

다만 건물의 오른쪽 점은 높이를 음수로 저장하여 정렬하게 하여 같은 위치에 여러 건물의 양 끝점이 있다면 아래와 같이 정렬하였습니다.

왼쪽 + 높음 > 왼쪽 + 낮음 > 오른쪽 + 낮음 > 오른쪽 + 높음

음수로 저장한 이유는 아래에서 추가적으로 설명하겠습니다.

2. 각 건물의 좌표에서의 최대 높이 구하기

PriorityQueue로 해당 위치에서 제일 높은 높이를 저장할 수 있게 구현했습니다.

1번에서 정렬된 위치의 높이를 확인했을 때 양수면 해당 높이를 PriorityQueue에 넣고 음수면 해당 높이를 PriorityQueue에서 뺐습니다.그렇게 되면 왼쪽에서 부터 모든 건물들의 높이를 보되 제일 높은 위치를 PriorityQueue에서 확인할 수 있고 건물의 오른쪽 위치를 발견하면 해당 높이를 PriorityQueue에서 제거하여 스카이라인 외곽선을 확인하게 했습니다.

직전 스카이라인의 높이와 현재 높이가 다르다면 해당 위치와 높이를 저장했습니다. 그 부분이 스카이라인에서 수직으로 변하는 부분이기 때문입니다.

코드는 아래와 같습니다.

class Solution {
    class Point implements Comparator<Point> {
        int pos;
        int height;

        public Point() {

        }

        public Point(int pos, int height) {
            this.pos = pos;
            this.height = height;
        }

        @Override
        public int compare(Point p1, Point p2) {
            if (p1.pos == p2.pos) {
                return Integer.compare(p2.height, p1.height);
            }
            return Integer.compare(p1.pos, p2.pos);
        }
    }

    public List<List<Integer>> getSkyline(int[][] buildings) {
        List<Point> points = new ArrayList<>();
        for (int[] building : buildings) {
            points.add(new Point(building[0], building[2]));
            points.add(new Point(building[1], -building[2]));
        }
        Collections.sort(points, new Point());

        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        pq.offer(0);
        int prevMax = 0;

        List<List<Integer>> result = new ArrayList<>();
        for (Point point : points) {
            if (point.height > 0) {
                pq.offer(point.height);
            }
            else {
                pq.remove(-point.height);
            }

            int currMax = pq.peek();
            if (prevMax != currMax) {
                result.add(new ArrayList<>(List.of(point.pos, currMax)));
                prevMax = currMax;
            }
        }

        return result;
    }
}

성능향상을 위해 PriorityQueue를 TreeMap으로 바꿨습니다. PriorityQueue에서 원소를 제거하면 O(N)이지만 TreeMap에서 원소를 제거하면 O(NlogN)이기 때문입니다.

TreeMap은 키의 중복이 허용되지 않기에 count를 값으로 주어 현재 해당 위치에 같은 높이의 점이 몇개 있는지를 세주었습니다.

코드는 아래와 같습니다.

class Solution {
    class Point implements Comparator<Point> {
        int pos;
        int height;

        public Point() {

        }

        public Point(int pos, int height) {
            this.pos = pos;
            this.height = height;
        }

        @Override
        public int compare(Point p1, Point p2) {
            if (p1.pos == p2.pos) {
                return Integer.compare(p2.height, p1.height);
            }
            return Integer.compare(p1.pos, p2.pos);
        }
    }

    public List<List<Integer>> getSkyline(int[][] buildings) {
        List<Point> points = new ArrayList<>();
        for (int[] building : buildings) {
            points.add(new Point(building[0], building[2]));
            points.add(new Point(building[1], -building[2]));
        }
        Collections.sort(points, new Point());

        TreeMap<Integer, Integer> heightMap = new TreeMap<>(Collections.reverseOrder());
        heightMap.put(0, 1);
        int prevMax = 0;

        List<List<Integer>> result = new ArrayList<>();
        for (Point point : points) {
            if (point.height > 0) {
                heightMap.put(point.height, heightMap.getOrDefault(point.height, 0) + 1);
            }
            else {
                int heightCnt = heightMap.get(-point.height);
                if (heightCnt == 1) {
                    heightMap.remove(-point.height);
                }
                else {
                    heightMap.put(-point.height, heightCnt - 1);
                }
            }

            int currMax = heightMap.firstKey();

            if (prevMax != currMax) {
                result.add(new ArrayList<>(List.of(point.pos, currMax)));
                prevMax = currMax;
            }
        }

        return result;
    }
}

처음에는 건물의 시작과 끝을 boolean으로 주려고 했지만 오히려 가독성이 떨어지고 compare 메소드가 깔끔해지지 않아 음수를 활용했습니다. 생각보다 고민이 필요한 문제였습니다.

의견 및 질문은 늘 환영합니다 :)

문제

m x n의 integer 행렬이 있을때, 만약 어떤 원소의 값이 0이라면 해당 행과 열을 모두 0으로 만들어야 한다.

해당 변수에 직접 수정해야 한다.

예시

Input: matrix = [[1,1,1],[1,0,1],[1,1,1]]
Output: [[1,0,1],[0,0,0],[1,0,1]]

Input: matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
Output: [[0,0,0,0],[0,4,5,0],[0,3,1,0]]

제약조건

m == matrix.length
n == matrix[0].length
1 <= m, n <= 200
-231 <= matrix[i][j] <= 231 - 1

풀이 : 구현

쉬운 문제처럼 보이지만 살짝 함정이 있어 두 번 정도 고치면서 풀었다.

1. 0이 보이면 해당 행과 열을 모두 0으로 만들기

행렬의 모든 원소를 방문하다가 원소가 0이면 해당 원소의 행과 열을 0으로 만들었다.

하지만 이는 잘못된 논리였다.

방문하지 않은 원소를 0으로 만들어버리면 방문했을 때 해당 원소의 행과 열도 0으로 만들었다. 기각!

2. boolean 행렬으로 값이 변한 원소인지 확인하기

1번과 비슷하되 비교 연산을 하나 더했다.

boolean 행렬로 0으로 바뀐 원소인지 아닌지를 체크해서 원소가 0이라도 변한적이 있다면 다른 행과 열에 영향을 끼치지 않게 했다.

음, 작동이 잘 되었지만 조금 더 보완할 수 있을 것 같았다. 보류!

3. 0으로 바꿀 boolean 배열 확인하기

행렬의 모든 원소를 방문하다가 원소가 0이면 해당 행과 열에 해당하는 index에 true 값을 줬다.

그 후, 다시 모든 원소를 방문하고, 행이든 열이든 boolean 배열의 값이 true라면 해당 원소를 0으로 줬다. 통과!

코드는 아래와 같습니다.

class Solution {
    public void setZeroes(int[][] matrix) {
        boolean[] rowZero = new boolean[matrix.length];
        boolean[] colZero = new boolean[matrix[0].length];
        
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                if (matrix[i][j] == 0) {
                    rowZero[i] = true;
                    colZero[j] = true;
                }
            }
        }

        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                if (rowZero[i] || colZero[j]) {
                    matrix[i][j] = 0;
                }
            }
        }        
    }
}

어렵진 않으나 실수하기 쉬운 구현 문제였습니다.

의견 및 질문은 늘 환영합니다 :)

문제

중복되지 않은 숫자 후보인 배열과 integer 타겟이 주어지고, 숫자 후보들을 선택해 만든 조합의 합이 타겟이 되는 중복되지 않는 조합들의 list를 반환해야 합니다. 조합은 어떤 순서로 반환해도 됩니다.

같은 숫자를 몇 번이든 선택해도 좋습니다. 두 조합이 있을 때, 선택된 숫자의 횟수가 다르다면 중복되지 않는 조합이라고 할 수 있습니다.

더해서 타겟이 되는 조합의 수는 150개 미만으로 테스트케이스가 주어집니다.

예시

Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]

2와 3이 후보라면, 2 + 2 + 3 = 7. 2가 여러 번 사용 되었습니다.
7이 후보라면, 7 = 7.
두 조합 밖에 없습니다.

Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]

Input: candidates = [2], target = 1
Output: []

주어진 후보에서 1을 만들 수 있는 조합은 없습니다.

풀이 : Backtracking

문제를 봤을 때 직관적으로 푼다면 제일 작은 숫자를 최대한 선택하고 타겟이 되는지 확인하고, 된다면 해당 조합을 저장하면 될 것 같았다.

그 후 넣었던 작은 숫자를 빼고 그 다음 큰 숫자를 넣어보는 방식으로 처리하면 될 것 같다 생각했다.

물론 합이 타겟을 넘어도 다음 숫자를 넣을 만큼 기존 숫자를 빼야한다.

예시 1번 이라면 2를 4번까지 넣었을 때 8이기에 다음으로 큰 숫자인 3을 넣을 수 있게 2개를 뺀 후 넣으면 첫번째 조합인 [2, 2, 3]이 된다.

처음에는 for 문으로 작성하면 될려나 했지만, 가능은 하겠지만 조건식이 복잡할 것 같다는 생각이 들어 recursive한 방식으로 진행하는게 좋다고 생각났다. 처음 생각한 아이디어에서 크게 벗어나지 않고 깔끔하게 코드를 작성해 보았다.

recursive 하게 첫 숫자 후보부터 모든 숫자를 넣어 합이 타겟이 되는지 확인한다.

합이 타겟이 된다면 해당 조합을 저장한다.

합이 타겟보다 크면 해당 조합에서는 어떤 숫자를 더 넣어도 타겟보다 클테니 그 전의 조합으로 돌아간다.

합이 타겟보다 작으면 해당 조합에 숫자 후보를 한 번 더 넣어서 recursive 하게 조합을 추가한다.

코드는 아래와 같습니다.

class Solution {
    List<Integer> comb = new ArrayList<>();
    List<List<Integer>> ans = new ArrayList<>();

    public void combination(int[] candidates, int target, int idx) {
        if (target < 0) return ;
        if (target == 0) {
            ans.add(new ArrayList<>(comb));
            return ;
        }

        for (int i = idx; i < candidates.length; i++) {
            comb.add(candidates[i]);
            combination(candidates, target - candidates[i], i);
            comb.remove(comb.size() - 1);
        }
    }

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        combination(candidates, target, 0);
        return ans;
    }
}

참고로 조합의 합을 확인하는 방식이 아니라 처음 타겟에서 숫자 후보를 계속 빼서 0이 되는지 아닌지 확인하는 방식으로 진행했습니다.

모든 조합을 추출하되, 어떤 조건에서는 더 추출할 필요가 없는지 조건을 걸면 되는 전형적인 backtracking 문제였습니다.

의견 및 질문은 늘 환영합니다 :)

문제

당신은 계단을 오르고 있습니다. 정상까지 n개의 계단을 올라가야 합니다.

한 번 오를 때 1개나 2개의 계단을 올라갈 수 있습니다.

몇 개의 중복되지 않은 방법으로 정상에 올라갈 수 있을까요?

예시

Input : n = 2

Output : 2

1. 1계단 + 1계단

2. 2계단

Input : n = 3

Output : 3

1. 1계단 + 1계단 + 1계단

2. 1계단 + 2계단

3. 2계단 + 1계단

풀이 : DP

문제를 딱 보자마자 "아 이건 규칙이 있다!" 라고 생각했습니다.

쉽게 떠올릴 수 있는 피보나치 문제랑 비슷하다고 느꼈고 빠르게 풀었습니다.

1개의 계단일 경우는 1가지 방법 (1)

2개의 계단일 경우는 2가지 방법 (1 + 1, 2)

3개의 계단일 경우는 3가지 방법 (1 + 2 / 1 + 1 + 1, 2 + 1)

4개의 계단일 경우는 4가지 방법 (1 + 1 + 2, 2 + 2 / 1 + 2 + 1, 1 + 1 + 1, 2 + 1 + 1)

계속 이어가다 보면 n - 2의 가짓수와 n - 1의 가짓수를 더하면 계단이 n개일 때의 방법의 갯수를 알 수 있습니다.

$$ n = (n-1) + (n-2) $$

코드는 아래와 같습니다.

class Solution {
    public int climbStairs(int n) {
        if (n == 1)
            return 1;
        
        int[] ways = new int[n + 1];

        ways[0] = ways[1] = 1;

        for (int i = 2; i <= n; i++) {
            ways[i] = ways[i - 1] + ways[i - 2];
        }

        return ways[n];
    }
}

DP문제를 처음 접하기에 좋은 문제 같습니다.