백준 9095번: 1, 2, 3 더하기 with Java

 

1, 2, 3 더하기 성공다국어

한국어   

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초 (추가 시간 없음)

512 MB

143885

95446

66567

64.943%

문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

• 1+1+1+1
• 1+1+2
• 1+2+1
• 2+1+1
• 2+2
• 1+3
• 3+1

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.

출력

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

예제 입력 1 복사

3
4
7
10

예제 출력 1 복사

7
44
274

출처

ICPC > Regionals > Asia Pacific > Korea > Asia Regional - Taejon 2001 연습 세션 PC번

• 문제를 번역한 사람: baekjoon
• 문제의 오타를 찾은 사람: standardraccoon, wjrqur1200

알고리즘 분류

• 다이나믹 프로그래밍

 

---

 

아니 이거 왜 성공 돼있어...?

보니까 2-1 수업에서 DP 배우다가 풀었나보다

역시 나는 퇴화한게 맞는 듯...

 

까묵었으니까 다시 풀어봅니다 하하핳하하하하하ㅏㅈㅅ

함 풀어보고 넘 빨리 풀면 한 개 더 풀지 모~

 

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

• 1+1+1+1
• 1+1+2
• 1+2+1
• 2+1+1
• 2+2
• 1+3
• 3+1

-> 뭐냐고.. 순서 바뀌면 다른 거로 치네 이...이건 그... 순열??

 

내가 생각한 건 1 2 3 쪼개기 횟수를 기억해놓고 4부터는 그 앞 번호 기억해 놓은 거에 1씩 더하기.... 생각했느데 좀 모자란 것 같기도 하고 함냐함냐 

 

앞 전 생각은 코드 짜면서 1 2 3 만 생각ㄱ해봐도 깨졌다 이게 무슨!!!!!

그러면은 3으로 나눈다 = 몫... 몫 곱하기 3 나누기 아 개망 이게 뭐임

그러면 4가 7이니까. 

1 => 1

2 => 2

3 => 4 

이렇게 나왔는데 혹시 앞 거 3개 더하는 건가?

 

근데 왜? 

일단 ㄱㄱ해보자

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int T = Integer.parseInt(br.readLine());
        int[] count = new int[11];    // 1부터 10까지 배열.. 0은 걍 버리자
        
        count[0] = 0;    // 혹시 모르니까 초기화
        count[1] = 1;    // 1은 1밖에 없잖아
        count[2] = 2;    // 1 + 1, 2
        count[3] = 4;    // 1 + 1 + 1, 1 + 2, 2 + 1, 3
        
        for (int i = 4; i < 11; i++) {
            count[i] = count[i - 1] + count[i - 2] + count[i - 3];
        }
        
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < T; i++) {
            int n = Integer.parseInt(br.readLine());
            sb.append(count[n]).append("\n");
        }
        
        System.out.println(sb);
	} 
}

 

 

이게.. 되네?

왜 되냐고

 

 

💡 문제: n을 1, 2, 3의 합으로 나타내는 방법 수

예를 들어 n = 4일 때,

• 1 + (3을 만드는 방법)
• 2 + (2를 만드는 방법)
• 3 + (1을 만드는 방법)

즉, 마지막에 더한 숫자가 1, 2, 3 중 어떤 것이냐에 따라 경우를 나눌 수 있어요.

---

✅ 예시로 풀어보기

예) n = 4

• 마지막 숫자가 1이면 → 앞에 3을 만드는 경우의 수 필요 → count[3]
• 마지막 숫자가 2이면 → 앞에 2를 만드는 경우의 수 필요 → count[2]
• 마지막 숫자가 3이면 → 앞에 1을 만드는 경우의 수 필요 → count[1]

 

 

---

✅ 점화식으로 일반화

왜냐하면 n을 만드는 방법은,

• n-1을 만든 다음 +1 하는 방법
• n-2를 만든 다음 +2 하는 방법
• n-3을 만든 다음 +3 하는 방법

을 모두 합한 것이기 때문입니다.

---

📌 비유로 이해해보기

예를 들어 10층 계단을 오를 때, 한 번에 1, 2, 3칸씩 오를 수 있다고 해볼게요.
그럼 10층까지 오르는 방법 수는?
→ 9층에서 1칸 오르기, 8층에서 2칸, 7층에서 3칸
즉, ways[10] = ways[9] + ways[8] + ways[7]

 

 

 

🧱 점화식의 의미

저는 n을 만들기 위한 방법을 세 가지로 나누어 생각해 보았습니다.

예를 들어 n = 4라고 해볼게요.

4를 만드는 방법을 구할 때,
마지막에 어떤 수를 더했는지를 기준으로 나눌 수 있습니다.

• 마지막에 1을 더했다면?
  → 그 전에는 3을 만들었을 것입니다.
  → 즉, 4를 만들 수 있는 방법 중, 1을 마지막에 붙인 경우의 수는 count[3]
• 마지막에 2를 더했다면?
  → 그 전에는 2를 만들었을 것입니다.
  → 그 경우의 수는 count[2]
• 마지막에 3을 더했다면?
  → 그 전에는 1을 만들었을 것입니다.
  → 그 경우의 수는 count[1]

따라서, count[4]는 이 세 가지 경우를 모두 합한 값입니다

 

 

 

그니까 얘가 1 + 1 + 2 이렇게 순서를 따지니까...

마지막에 더한 애가 1 2 3 인 거에 따라 경우가 달라지니까 앞에 거 1 2 3 빼고 그 3가지를 더하는 거다 !!!

오케??