[파이썬 풀이] 25345번: 루나의 게임 세팅 - 백준

2022. 8. 17. 05:23· 🌀 알고리즘(Algorithm)/백준(문제 풀이)
728x90
반응형

백준 25345번: 루나의 게임 세팅

알고리즘 분류: 수학. 조합론

파이썬(Python) 풀이

 

링크: https://www.acmicpc.net/problem/25345

문제

루나와 리나는 타워 건설 게임을 하려고 한다. 타워 건설 게임은 K개의 타워를 사용하는 게임이고 루나는 이 게임을 세팅하려고 한다.

게임 세팅은 서로 다른 높이의 N개의 타워 중 K개를 선택해 원하는 순서로 일렬로 배치하는 것이다. 이때 앞과 뒤에서 바라볼 때 모든 타워가 최소 한 번은 보여야 한다. 즉, 어떤 타워에 대해서 그보다 높은 타워가 그 타워의 앞쪽과 뒤쪽에 모두 존재하면 안된다는 것이다. 

게임 세팅을 하던 루나는 문득 게임을 세팅하는 방법이 얼마나 많을 지가 궁금해졌다. 루나를 도와서 게임 세팅을 하는 경우의 수를 구해보자. 


입력

첫째 줄에는 두 양의 정수 N과 K가 주어진다.

둘째 줄에는 각각의 타워의 높이 A₁,A₂,⋯,An이 공백으로 구분되어 주어진다.

모든 입력은 정수이다.


출력

게임 세팅을 할 수 있는 경우의 수를 10⁹+7로 나눈 나머지를 출력한다. 


풀이

이 문제의 예제는 한개가 주어진다.

입력과 출력은 다음과 같다.

# 입력
5 3
1 6 7 9 11

# 출력
40

타워의 개수는 5개, 그리고 3개의 타워를 이용했을 때의 경우의 수를 구하는 것이다.

 

이 문제에 대하여, 예제를 통해 설명하자면

먼저 타워 5개중 사용할 3개를 뽑아야 하는 경우의 수 : 5C3 = 10가지

그렇게 뽑힌 타워가, 높이가 6, 9, 11일 때,

 

[6, 9, 11]

[6, 11, 9]

[9, 11, 6]

[11, 9, 6] 이렇게 4가지이다.

따라서 10 * 4 = 40가지가 나온다.


 

그러면 어떻게 이런 생각을 떠올릴 수 있는것인가? 라고 한다면,

답은 크기가 가장 큰거부터 세우면 된다.

먼저 높이가 11인 타워를 세운다.

 

 

그리고 그 타워를 기준으로 높이가 9인 타워를 어느쪽에 세울 지 정한다. 

 

그렇게 높이가 9인 타워를 세웠다면, 그 다음의 높이가 6인 타워를 양쪽중 어느쪽에 세울지 정한다.

 

그렇게 되면 다음과 같은 결과가 나타난다.

 

이걸 단순화 한다면 K개중에 높이가 가장 큰걸 제외한 K-1개가 각각 왼쪽, 오른쪽인 2개의 방향중 한 방향을 고르는 것이므로

2ⅡK-1 = 2^(K-1)라고 볼 수 있다.

 

따라서 NCK * 2^(K-1)라고 정리할 수 있다.


 

코드로 구현하면 다음과 같다.

factorial을 math모듈에서 선언한 뒤, N과 K를 입력받고, 배열 arr을 (솔직히 의미없긴하지만) 입력 받고,Combination 식을 기반으로 그대로 쓰면 된다. 또한 마지막에 10의 9제곱 + 7의 나머지로 구하는 것도 잊지 말아야 한다.

 

728x90
반응형
저작자표시 (새창열림)

'🌀 알고리즘(Algorithm) > 백준(문제 풀이)' 카테고리의 다른 글

[파이썬 풀이] 11687번: 팩토리얼 0의 개수 - 백준  (1) 2024.01.20
fflush(stdin)을 쓰지말자...  (0) 2023.12.08
[파이썬 풀이] 1152번: 단어의 개수 - 백준  (0) 2022.08.14
[파이썬 풀이] 17202번: 핸드폰 번호 궁합 - 백준  (0) 2022.07.28
[파이썬 풀이] 24039번: 2021은 무엇이 특별할까? - 백준  (0) 2022.07.19
'🌀 알고리즘(Algorithm)/백준(문제 풀이)' 카테고리의 다른 글
  • [파이썬 풀이] 11687번: 팩토리얼 0의 개수 - 백준
  • fflush(stdin)을 쓰지말자...
  • [파이썬 풀이] 1152번: 단어의 개수 - 백준
  • [파이썬 풀이] 17202번: 핸드폰 번호 궁합 - 백준
Dodolist
Dodolist
소프트웨어 및 하드웨어에 대한 지식 및 시행착오 기록 사이트
도돌이의 세미프로그래밍소프트웨어 및 하드웨어에 대한 지식 및 시행착오 기록 사이트
Dodolist
도돌이의 세미프로그래밍
Dodolist
전체
오늘
어제
  • 분류 전체보기 (68)
    • 💻 소프트웨어(SW) (29)
      • HTML | JS | CSS (6)
      • Python (5)
      • Swift (9)
      • MySQL (4)
      • 프로젝트 (4)
    • 🌀 알고리즘(Algorithm) (9)
      • 백준(문제 풀이) (9)
    • ✏️나를 되돌아보는, 글 (13)
      • 진지한 글 (9)
      • 뻘글 (4)
    • 📚 지식글 (14)
    • 거인의 무릎에 올라타기 (2)

블로그 메뉴

  • | Home
  • | Miruzima
  • | Instagram

인기 글

최근 글

최근 댓글

hELLO · Designed By 정상우.v4.2.2
Dodolist
[파이썬 풀이] 25345번: 루나의 게임 세팅 - 백준
상단으로

티스토리툴바

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.