[BOJ] 2407번: 조합

2022. 5. 2. 23:31· BOJ 백준/다이나믹 프로그래밍
목차
  1. 문제
  2. 입력
  3. 출력
  4. 풀이
  5. 코드
  6. 결과
728x90
반응형

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을 출력한다.


풀이

조합의 성질인 n C r + n C r+1 = n+1 C r+1 을 이용한다.

그런데 조합의 결과값이 int 범위를 벗어나므로 string 배열을 사용하여 계산해야 한다.

string도 vector처럼 push와 pop을 할 수 있고 reverse함수를 이용하여 배열을 역으로 바꿀 수 있다.

 

 

코드

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int n, m;
string com[101][101];

string add(string num1, string num2) {
  string num = "";
  int sum = 0;

  while(!num1.empty() || !num2.empty() || sum) {
    if(!num1.empty()) {
      sum += num1.back() - '0';
      num1.pop_back();
    }
    if(!num2.empty()) {
      sum += num2.back() - '0';
      num2.pop_back();
    }
    num.push_back((sum%10)+'0');
    sum /= 10;
  }

  reverse(num.begin(), num.end());
  return num;
}

string find(int a, int b) {
  if(b==0 || b==a) return "1";

  string &num = com[a][b];
  if(num != "") return num;
    
  num = add(find(a-1,b-1),find(a-1,b));
  return num;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  cin >> n >> m;
  cout << find(n, m);
  return 0;
}

처음에 int 배열을 사용하여 풀었지만 int 범위를 벗어날 수 있다는 것을 알았다.

 

결과

728x90
반응형

'BOJ 백준 > 다이나믹 프로그래밍' 카테고리의 다른 글

[BOJ] 1309번: 동물원  (0) 2022.08.16
[BOJ] 13398번: 연속합 2  (2) 2022.08.15
[BOJ] 1149번: RGB거리  (0) 2022.04.21
[BOJ] 17626번: Four Squares  (0) 2022.03.09
[BOJ] 2579번: 계단 오르기  (0) 2021.08.20
  1. 문제
  2. 입력
  3. 출력
  4. 풀이
  5. 코드
  6. 결과
'BOJ 백준/다이나믹 프로그래밍' 카테고리의 다른 글
  • [BOJ] 1309번: 동물원
  • [BOJ] 13398번: 연속합 2
  • [BOJ] 1149번: RGB거리
  • [BOJ] 17626번: Four Squares
코블리_vv
코블리_vv
코블리_vv
코딩 놀이터
코블리_vv
전체
오늘
어제
  • 분류 전체보기 (67)
    • CS 노트 (1)
    • 대외활동 (0)
      • 창업 동아리 (0)
    • AWS (0)
      • AWS Academy Cloud Architect.. (0)
      • AWS Lab (0)
    • 웹 개발 노트 (3)
      • 웹 프로젝트 (0)
      • 스프링 인 액션 (0)
      • 스프링 입문을 위한 자바 객체 지향의 원리와 이해 (0)
    • ORACLE (0)
    • TOPCIT (2)
      • M1 소프트웨어 개발 (2)
      • M2 데이터 이해와 활용 (0)
    • 캡스톤 (5)
    • BOJ 백준 (53)
      • 브루트포스 (1)
      • 정렬 (6)
      • 이분탐색 (5)
      • 맵 (2)
      • 다이나믹 프로그래밍 (11)
      • 수학 (5)
      • 그리디 (3)
      • 분할정복 (4)
      • DFS (3)
      • BFS (6)
      • 그래프 (4)
      • 자료구조 (1)
      • 백트래킹 (2)
    • 코딩 테스트 (0)
      • 코드트리 (0)
    • 대회 (0)
    • Spring Boot (3)
      • JPA (3)

블로그 메뉴

  • 홈
  • 태그
  • 알고리즘
  • BOJ 백준
  • 방명록

공지사항

인기 글

태그

  • BFS
  • 암호학
  • 다이나믹 프로그래밍
  • 백준 n과m
  • 너비우선탐색
  • backtrader
  • 스프링인액션
  • 그리디 알고리즘
  • dfs
  • 1676
  • 플로이드 와샬
  • dp
  • 백준 토마토
  • 시스템 트레이딩
  • 파이썬 backtrader
  • java
  • 분할정복
  • n과m
  • 컴퓨터 보안
  • 이분탐색
  • 웹개발
  • computer security
  • binary search
  • 다이나믹프로그래밍
  • 우선순위 큐
  • 재귀
  • 투자 전략
  • 투자
  • 백트래킹
  • spring

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.2
코블리_vv
[BOJ] 2407번: 조합
상단으로

티스토리툴바

개인정보

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

단축키

내 블로그

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

블로그 게시글

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

모든 영역

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

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