BOJ

[실버 4] 2407번: 조합

2022. 9. 11. 22:52
목차
  1. 문제
  2. 입력
  3. 출력
  4. 사고의 흐름
  5. 내가 작성한 소스코드
  6. 피드백
  7. 여담
728x90

Original Source: https://www.acmicpc.net/problem/2407

 

2407번: 조합

n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n)

www.acmicpc.net


문제

nCm을 출력한다.

입력

n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n)

출력

nCm을 출력한다.


사고의 흐름

더보기
  • m, n의 상한이 100인데 재귀로 풀 수 있을까? Python으로는 힘들어 보이는데. 일단 해보고 안 되면 Pypy로 제출해보고, 그래도 안 되면 C++로 짜든지 다른 방법을 쓰든지 하자.
  • 역시 시간 초과가 뜨네. 다른 방법을 쓰자. DP 쓰면 되겠네.

내가 작성한 소스코드

# 시간 초과

import sys
input = sys.stdin.readline


def get_combination(x, n, r, li, depth):
    global cnt
    
    if len(li) == r:
        cnt += 1
        return
    
    if depth == n:
        return

    li.append(sample[x])
    get_combination(x+1, n, r, li, depth+1)
    del li[-1]
    get_combination(x+1, n, r, li, depth+1)


n, m = map(int, input().split())
sample = [i for i in range(n)]
global cnt
cnt = 0

get_combination(0, n, m, [], 0)
print(cnt)
import sys
input = sys.stdin.readline


def get_combination(n, r, dp):
    if n == r or r == 0:
        return 1

    if dp[n][r] != -1:
        return dp[n][r]
    
    dp[n][r] = get_combination(n-1, r, dp) + get_combination(n-1, r-1, dp)
    return dp[n][r]


n, m = map(int, input().split())
dp = [[-1] * (m+1) for _ in range(n+1)]

print(get_combination(n, m, dp))

피드백

  • 최대한 다른 사람의 코드를 보면서 문제 푸는 시간을 단축시키자. 설령 그대로 따라 치는 한이 있더라도 다른 코드를 보면서 사고의 지평을 넓혀야 한다.

여담

 백준 6603번 문제를 재귀 함수로 푸는 방법이 이해가 안 되서 풀어보았다. 이전에 작성한 코드를 참고하면서 재귀로도 풀긴 했는데 아직도 잘 모르겠다. 정말 재귀 함수는 이해가 될 것 같다가도 다시 모르겠다….

저작자표시 (새창열림)

'BOJ' 카테고리의 다른 글

[골드 4] 13913번: 숨바꼭질 4  (0) 2022.09.14
[실버 1] 1697번: 숨바꼭질  (0) 2022.09.12
[실버 2] 6603번: 로또  (0) 2022.09.10
[골드 4] 9019번: DSLR  (0) 2022.09.09
[실버 3] 11726번: 2×n 타일링  (0) 2022.09.07
  • 문제
  • 입력
  • 출력
  • 사고의 흐름
  • 내가 작성한 소스코드
  • 피드백
  • 여담
'BOJ' 카테고리의 다른 글
  • [골드 4] 13913번: 숨바꼭질 4
  • [실버 1] 1697번: 숨바꼭질
  • [실버 2] 6603번: 로또
  • [골드 4] 9019번: DSLR
Park Joonyoung
Park Joonyoung
개발 블로그
Park Joonyoung
DevJoon
Park Joonyoung
전체
오늘
어제
  • 분류 전체보기 (88)
    • BOJ (41)
      • 틀렸습니다 (6)
    • 알고리즘 (4)
    • C++ (2)
    • Python (1)
    • 토이 프로젝트 (0)
    • 선형대수학 (1)
    • 기타 (3)
    • 에세이 (4)
    • [개인 보관용] (32)
      • 이코테 강의 정리 (0)
      • 알고리즘(old) (0)
      • 단변수미적분학 (0)
      • 다변수미적분학 (0)
      • 선형대수학 (32)
      • 선형대수학(old) (0)
      • 프랑스어 (0)
      • 독서노트 (0)
      • 사진 (0)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 백준
  • git bash
  • bfs
  • stl
  • 백트래킹
  • Python
  • github
  • dfs
  • 그리디
  • 시뮬레이션
  • 브루트포스
  • 수학
  • DP
  • 개발
  • DevJoon
  • 에세이
  • Notion
  • It
  • 알고리즘
  • 코딩테스트
  • 구현
  • next_permutation
  • 선형대수학
  • c++
  • BOJ
  • ps

최근 댓글

최근 글

hELLO · Designed By 정상우.
Park Joonyoung
[실버 4] 2407번: 조합
상단으로

티스토리툴바

단축키

내 블로그

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

블로그 게시글

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

모든 영역

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

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