코딩테스트 & 문제 풀이

[Python]백준_17358 : 복불복으로 지구 멸망

2023. 11. 9. 00:39

2022년 12월 26일에 작성됨

 

https://www.acmicpc.net/problem/17358

 

17358번: 복불복으로 지구 멸망

(2,1,4,3), (3,4,1,2), (4,3,2,1) 총 3가지 경우가 가능하다.

www.acmicpc.net

 

 

문제 분석

쉽게 예를 들어 1, 2, 3, 4, 5, 6번의 6개의 컵이 있다고 가정해보자.

1번 컵이랑 어느 컵의 위치를 바꿀지 5개의 경우의 수(2, 3, 4, 5, 6)가 있다.
1번과 6번을 택한다고 하면 남은 컵은 2, 3, 4, 5번 컵이 있다.

2번 컵이랑 어느 컵의 위치를 바꿀지 3개의 경우의 수(3, 4, 5)가 있다.
2번과 4번을 택한다고 하면 남은 컵은 자동으로 3번과 5번이 된다.

따라서 컵이 6개일 때의 경우의 수는 5 * 3 * 1 = 15가 된다.
이를 식으로 나타내면 (n-1) * (n-3) * (n-5)

즉, n개의 컵일 때 경우의 수는 (n-1) * ((n-1)-2) * ((n-1)-4) ... * 1 이다.

 

 

소스 코드 (⭕)

N = int(input())
cnt = 1

while N:                     # N이 0 이하가 되는 순간 반복을 멈춤
    cnt *= N-1               # 경우의 수를 계속 곱한다
    N -= 2                   # N에서 2씩 뺀다

print(cnt % 1000000007)

 

코드 분석

1. 음료의 개수 N을 입력 받는다. (N은 무조건 짝수여야 함)

2. while문을 이용해서 반복을 하면서 매 반복마다 음료 두 개를 택해서 위치를 바꾸므로 cnt와 N-1을 누적하여 곱해준다.

3. 그 다음 n에서 2씩 빼고 n이 0 이하가 되는 순간 반복을 중단 하도록 한다.

4. cnt를 10^9 + 7로 나눈것의 나머지가 경우의 수가 된다.

 

 

 

end

코테는 수학 능력이 정말 중요한 것 같다
규칙을 찾아서 공식을 유도하는 과정이 혼자하기엔 아직 많이 어렵다ㅠㅠ

 

 

 

'코딩테스트 & 문제 풀이' 카테고리의 다른 글

[Python]백준_5566 : 주사위 게임  (0) 2023.11.10
[Python]백준_13301 : 타일 장식물  (2) 2023.11.09
[Python]백준_25373 : 벼락치기  (1) 2023.11.08
[Python]백준_25643 : 문자열 탑 쌓기  (0) 2023.11.07
[Python]백준_2057 : 팩토리얼 분해  (1) 2023.11.06
  1. 문제 분석
  2. 소스 코드 (⭕)
  3. 코드 분석
  4. end
'코딩테스트 & 문제 풀이' 카테고리의 다른 글
  • [Python]백준_5566 : 주사위 게임
  • [Python]백준_13301 : 타일 장식물
  • [Python]백준_25373 : 벼락치기
  • [Python]백준_25643 : 문자열 탑 쌓기
Hicecream
Hicecream
Hicecream
Hicecream
Hicecream
전체
오늘
어제
  • 분류 전체보기 (203)
    • 코딩테스트 & 문제 풀이 (159)
    • 동아리 활동 (8)
    • 외부 활동 (0)
    • 대학 과제 (3)
    • Git & Git Hub (5)
    • 코딩 프로젝트 (4)
    • 공부 메모 (18)
    • 일상 (2)
    • 참고사항 (2)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • Bronze 4
  • 구현
  • python
  • Bronze 2
  • 수학
  • C언어 기초 100제
  • 사칙연산
  • Silver 5
  • Bronze 5
  • Bronze 3
  • Code up
  • 정렬
  • Silver 4
  • C
  • LV1
  • Java
  • 문자열
  • programmers
  • Bronze 1
  • BOJ

최근 댓글

최근 글

hELLO · Designed By 정상우.
Hicecream
[Python]백준_17358 : 복불복으로 지구 멸망
상단으로

티스토리툴바

단축키

내 블로그

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

블로그 게시글

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

모든 영역

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

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