[LeetCode] 1359번 문제를 풀어보았다. (ft. java)

2022년 03월 06일 일요일 - 오늘은 노가다로 품... ㅎㅎ

오늘 올려볼 문제는 1359번 Count All Valid Pickup and Delivery Options 이라는 문제이다.

사진을 클릭하면 해당 문제로 이동합니다.

오늘도 LeetCode 사이트 오늘의 문제를 가지고 왔다.

와 근데 다른 풀이 보니깐 개쩔더라

입력

사진에서도 볼 수 있듯이 int 값 하나가 입력으로 들어온다.

---

풀이 및 코드

int 값 개수만큼 pickup을 하고 delivery를 할 수 있는 경우의 수를 찾아서 리턴하는 문제다.

이 때 delivery는 무조건 pickup을 한 뒤에 가능하다.

오늘은 걍 노가다로 풀고 정답을 봤는데 진짜 생각도 못한 방법이 있었다.

일단 n이 1일 때를 그림으로 보자면 __ P1 __ D1 __ 과 같이 표현가능하다.

이 때 P2, D2를 넣을 수 있는 가지수를 생각해보면 3 + 2 + 1 이다.

P1 앞에 P2를 넣는 경우 <- D2는 P2 뒤에만 있으면 되므로 3가지 공백에 모두 들어갈 수 있음 (P2 바로 뒤까지 포함)
D1 앞에 P2를 넣는 경우 <- D2는 P2 뒤에만 있으면 되므로 2가지 공백에 들어갈 수 있음
D1 뒤에 P2를 넣는 경우 <- D2는 P2 뒤에만 있으면 되므로 1가지 공백에 들어갈 수 있음

즉 지금 구하려는 수의 1을 뺀 수로 계산해둔 값에 공백에 넣을 수 있는 가지수를 곱하기만 하면 이번에 나올 값을 쉽게 구할 수 있는 것이다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public int countOrders(int n) {
        long result = 1;
        int diff = 9, mul = 6;
        n--;
        while(n > 0)
        {
            result *= mul;
            mul += diff;
            diff += 4;
            result %= 1000000007;
            n--;
        }

        return (int)result;
    }
}

위에서 설명한 알고리즘 기법을 사용한 풀이다.

풀이코드

class Solution {
    public int countOrders(int n) {
        int mod = 1000000007;
        long result = 1;
        for(int i = 2; i <= n; i++)
        {
            int space = (i - 1) * 2 + 1;
            result = result * (space * (space + 1) / 2);
            result %= mod;
        }

        return (int)result;
    }
}

---

제출 화면

오늘 다른 사람들의 풀이를 보고 좀 충격을 받았다.

그렇게 어렵지 않은 접근이었는데 이걸 생각을 못했다는 것에 좀 화가났던 것도 있었던 것 같다.

그래도 문제는 풀었으니... 다행이라고 생각한다. ㅋㅋㅋㅋㅋㅋ

내일도 문제를 풀어서 블로그에 글을 쓸 수 있으면 좋겠다.