[백준/C++] 9095번 1, 2, 3 더하기

2022. 7. 6. 16:02· Koala - 7기/코딩테스트 준비 스터디
목차
  1. 문제 분석
  2. 코드
  3. 문제 풀이

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

 

9095번: 1, 2, 3 더하기

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.

www.acmicpc.net

 

문제 분석

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하라.

조건. n은 양수 이며 11보다 작다.

코드

#include <iostream>

using namespace std;

int n;
int cnt;

void caseNum(int num){
	if(num==0){
		cnt++;
		return;
	}
	for(int i=1; i<=3; i++){
		if(num-i>=0){
			caseNum(num-i);
		}
	}
}

int main(){
	cin>>n;
	int input[n];
	for(int i=0; i<n; i++) {
		cin>>input[i];
	}
	for(int i=0; i<n; i++) {
		cnt = 0;
		caseNum(input[i]);
		cout<<cnt<<"\n";
	}
	return 0;
}

문제 풀이

1. 테스트 케이스의 개수 n과 테스트 케이스 n개를 배열 input으로 입력받는다.

2. input의 값을 인자로 1, 2, 3의 합으로 나타내는 경우의 수를 구하는 caseNum 함수를 실행한다.

3. 1, 2, 3의 합으로 나타내야 하므로 i의 범위를 1부터 3이하로 설정하여 반복문을 실행한다.

4.  1, 2, 3의 합이 테스트 케이스보다 크면 안 되므로 num-i가 0 이상일 때만(0보다 작으면 1, 2, 3의 합이 테스트 케이스보다 크다는 뜻이기 때문)  num-i(테스트 케이스에서 1 또는 2 또는 3을 뺀 값)를 인자로 caseNum함수를 호출한다.

5. 이처럼 caseNum 함수를 재귀적으로 실행하다가 num이 0이 되면, 즉 경우(1, 2, 3의 합이 테스트 케이스와 일치할 때)가 완성되었다면, 경우의 수인 cnt를 1 증가시키고 함수를 종료한다.

6. 이후 반복문이 돌면서 계속해서 다음 경우를 완성시킬 때마다 cnt가 증가한다. 

(실행 예: 테스트 케이스: 3

  1. caseNum(3) 호출, i=1: caseNum(2) 호출
  2. caseNum(2)에서 i=1: caseNum(1) 호출
  3. caseNum(1)에서 i=1: caseNum(0) 호출
  4. caseNum(0)에서 num이 0이므로 경우 완성(1+1+1), cnt 증가, caseNum(0) 종료
  5. caseNum(1)에서 i=2: num-i가 -1이므로 caseNum(1) 종료
  6. caseNum(2)에서 i=2: caseNum(0) 호출
  7. caseNum(0)에서 num이 0이므로 경우 완성(1+2), cnt 증가, caseNum(0) 종료
  8. caseNum(2)에서 i=3: num-i가 -1이므로 caseNum(2) 종료
  9. caseNum(3)에서 i=2: caseNum(1) 호출 (이후 위와 비슷한 과정 반복)

)

7. cnt는 caseNum 함수 실행 전마다 0으로 초기화해줘야 각 테스트 케이스에 맞는 경우의 수를 구할 수 있다.

저작자표시 (새창열림)

'Koala - 7기 > 코딩테스트 준비 스터디' 카테고리의 다른 글

[백준/Python] 1895번 필터  (0) 2022.07.07
[백준/C++] 6603번 로또  (0) 2022.07.06
[백준/JAVA] 14939번 불 끄기  (0) 2022.07.05
[백준/C++] 13423번 Three Dots  (0) 2022.07.04
코딩테스트 준비 스터디 출석부  (0) 2022.07.03
  1. 문제 분석
  2. 코드
  3. 문제 풀이
'Koala - 7기/코딩테스트 준비 스터디' 카테고리의 다른 글
  • [백준/Python] 1895번 필터
  • [백준/C++] 6603번 로또
  • [백준/JAVA] 14939번 불 끄기
  • [백준/C++] 13423번 Three Dots
KauKoala
KauKoala
항공대 알고리즘 동아리 Koala 🥰
Koala항공대 알고리즘 동아리 Koala 🥰
KauKoala
Koala
KauKoala
전체
오늘
어제
  • 분류 전체보기 (1884)
    • 공지 게시판 (10)
    • 정보 게시판 (8)
    • Codeforce (15)
    • acm-icpc (6)
    • Koala - 1기 (16)
    • Koala - 2기 (111)
      • Programming Contest (1)
      • A반 (20)
      • B반 (39)
      • C반 (22)
      • 기초 강의 (18)
    • Koala - 3기 (10)
      • 기초 스터디 (7)
    • Koala - 4기 (67)
    • Koala - 5기 (144)
      • 기초 알고리즘 스터디 (75)
      • 코딩테스트 준비 스터디 (68)
    • Koala - 6기 (102)
      • 기초 알고리즘 스터디 (75)
      • 코딩테스트 준비 스터디 (25)
      • 모의 테스트 스터디 (1)
    • Koala - 7기 (167)
      • 기초 알고리즘 스터디 (97)
      • 코딩테스트 준비 스터디 (68)
      • 모의 테스트 스터디 (1)
    • Koala - 8기 (44)
      • 기초 알고리즘 스터디 (32)
      • 코딩테스트 준비 스터디 (10)
      • 코드포스 버츄얼 스터디 (0)
      • 프로그래머스 LV2 스터디 (0)
    • Koala - 9기 (205)
      • 기초 알고리즘 스터디 (138)
      • 코딩테스트 준비 스터디 (64)
      • 모의테스트 준비 스터디 (1)
    • Koala - 10기 (117)
      • 기초 알고리즘 스터디 (30)
      • 코딩테스트 준비 스터디 (86)
      • 모의테스트 준비 스터디 (1)
    • Koala - 11기 (151)
      • 기초 알고리즘 스터디 (46)
      • 코딩테스트 준비 스터디 (104)
      • 모의테스트 준비 스터디 (1)
    • Koala - 12기 (86)
      • 기초 알고리즘 스터디 (31)
      • 코딩테스트 준비 스터디 (55)
    • Koala - 13기 (119)
      • 기초 알고리즘 스터디 (52)
      • 코딩테스트 준비 스터디 (67)
    • Koala - 14기 (116)
      • 기초 알고리즘 스터디 (39)
      • 코딩테스트 준비 스터디 (77)
    • Koala - 15기 (138)
      • 기초 알고리즘 스터디 (73)
      • 코딩테스트 준비 스터디 (65)
    • Koala - 16기 (47)
      • 코딩테스트 기초 스터디 (16)
      • 코딩테스트 심화 스터디 (31)
    • Koala - 17기 (62)
      • 코딩테스트 기초 스터디 (15)
      • 코딩테스트 심화 스터디 (47)
    • Koala - 18기 (31)
      • 코딩테스트 기초 스터디 (11)
      • 코딩테스트 심화 스터디 (20)
    • Koala - 19기 (38)
      • 코딩테스트 기초 스터디 (7)
      • 코딩테스트 심화 스터디 (31)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

  • 🐨항공대 알고리즘 학회 Koala 3기 모집
  • 🐨항공대 알고리즘 학회 Koala 2기 모집
  • 소모임 소개

인기 글

태그

  • dp
  • 백준
  • dfs
  • C++
  • BOJ
  • 백트래킹
  • 파이썬
  • BFS

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.3.0
KauKoala
[백준/C++] 9095번 1, 2, 3 더하기
상단으로

티스토리툴바

단축키

내 블로그

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

블로그 게시글

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

모든 영역

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

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