사용자 도구

사이트 도구


ps:problems:boj:21739

펭귄 네비게이터

ps
링크acmicpc.net/…
출처BOJ
문제 번호21739
문제명펭귄 네비게이터
레벨골드 2
분류

카탈랑 수

시간복잡도O(n)
인풋사이즈n<=10000
사용한 언어Python 3.11
제출기록33240KB / 44ms
최고기록44ms
해결날짜2023/11/20

풀이

  • 결론적으로 카탈랑 수 (Catalan number)가 되기는 하는데, 변환과정이 직관적으로 떠오르지는 않는다.
  • 조건을 만족하기 위해서는, 어떤 칸에 들어가는 수는 그 칸보다 왼쪽이나 위쪽에 있는 칸에 있는 수보다 커야 한다.
  • 이런 조건을 만족하는 얼음길이 있다고 할때, 얼음길을 괄호 문자열로 변환할수가 있다.
  • 문자열의 i번째 글자를, i번 수가 얼음길의 위쪽 칸에 있으면 (, 아래쪽 칸에 있으면 )가 된다고 하자. 조건을 만족하는 얼음길은 올바른 괄호문자열이 된다.
  • 이렇게 n개의 괄호쌍으로 만들어지는 올바른 괄호문자열의 갯수와 동일한 문제가 되므로, 답은 카탈랑수가 되고 O(n)에 구할수 있다.

코드

"""Solution code for "BOJ 21739. 펭귄 네비게이터".

- Problem link: https://www.acmicpc.net/problem/21739
- Solution link: http://www.teferi.net/ps/problems/boj/21739

Tags: [catalan number]
"""

from teflib import combinatorics

MOD = 10**9 + 7


def main():
    N = int(input())
    print(combinatorics.catalan(N, MOD))


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
X B E U Q
 
ps/problems/boj/21739.txt · 마지막으로 수정됨: 2023/11/20 08:46 저자 teferi