[3주차_화요일] 15989_1, 2, 3 더하기 4

[Jewan1120]

• 사이트: 백준
• 문제: 1, 2, 3 더하기 4
• 번호: 15989번

[baexxbin]

🤔 시간복잡도 고려사항

• n <= 10,000
• DP를 떠올려 시간 내 가능할 것 같았음

💡 풀이 아이디어

• DP: 1,2,3 합으로 N을 만들 수 있는 방법 수를 구해야함
  • 하위 내용의 조합으로 타겟을 만들어감
• 점화식
  • dp[i][j]: i(1,2,3)으로 j만들기
  • dp[i][j] = dp[1][j-i] + dp[2][j-i] + dp[3][j-i]
    • i번째에서 j를 만들 수 있는 경우는, j-i의 값을 만들 수 있는 경우의 수
    • k로 둬서 자신(i)부터 1까지 돌 수 있도록 함
• 테스트 케이스의 가장 큰 값을 기준으로 dp배열 만듦

dp 잘 못해서... 점화식이 이쁘진 않은것 같다.

[KodaHye]

🤔 시간복잡도 고려사항

• 1, 2, 3의 개수를 0 ~ 10,000개 할 수 있는 경우를 모두 탐색한다면 시간 초과
• DP사용: O(N)

💡 풀이 아이디어

• 점화식: dp[i] = dp[i - 3] + n / 2 + 1
• dp[i - 3]: 3을 쓰면서 i를 만들 수 있는 경우의 수
• n / 2: 2를 쓰면서 i를 만들 수 있는 경우의 수
  • 2가 1개일 때, 2개일 때, ... n 개일 때 → n/2
• 1: 숫자가 모두 1인 경우

사실 질문 게시판 보다가 스포당해서 왜 이런 점화식이 나오는지 고민해봤습니다 ^_^,,ㅎ,,,,

[icegosimperson]

🤔 시간복잡도 고려사항

• n<=10,000, O(N * 3) => O(N)

💡 풀이 아이디어

• 초기값 : dp[0] = 1 (0을 1, 2, 3의 합으로 표현할 수 없지만 음수 인덱스 고려하여 1로 초기화)
• 점화식 : dp[n] = dp[n-1] + dp[n-2] + dp[n-3]
• i=1 1을 이용한 경우 계산, i=2 2를 이용한 경우 추가 계산, i=3 3을 이용한 경우 계산
• 중복 방지되는 이유 : 작은 수부터 차례로 계산하기에 이미 계산 된 결과에만 새로운 값을 더하기 때문

for(int i=1; i<=3; i++) { for(int j=i; j<10001; j++) { dp[j] += dp[j-i]; } }

int T = Integer.parseInt(br.readLine()); // 테스트 케이스 개수 T

for(int i=0; i<T; i++) { int N = Integer.parseInt(br.readLine()); System.out.println(dp[N]); }

- n값이 크지 않아서  먼저 dp배열 값을 모두 초기화해주는 방식으로 풀었는데, 
- n값이 커지면 비효율적일 것 같습니다

[yeongleej]

🤔 시간복잡도 고려사항

dp로 해결 : O(N)

💡 풀이 아이디어

• 모든 수는 1로 만들 수 있기 때문에 1로 초기화
• 2를 추가해서 만들 수 있는 경우의 수 추가

  dp[i] += d[i-2]

• 3을 추가해서 만들 수 있는 경우의 수 추가

  dp[i] += dp[i-3]

[Jewan1120]

🤔 시간복잡도 고려사항

• 1 ≤ n ≤ 10,000 → O(n^2) ~ O(n^3)
• 이전 값이 다음 값에 영향을 줄 수 있는 문제이므로 DP를 이용해서 풀이

💡 풀이 아이디어

for (int i = 1; i <= 3; i++)
    for (int j = i; j < 10_001; j++)
        dp[j] += dp[j - i];

• 모든 수는 1로 만들 수 있음
• 인덱스가 2씩 증가할 때마다 2이 현재 조합에 추가됨
• 인덱스가 3씩 증가할 때마다 3이 현재 조합이 추가됨

  dp 점화식 어렵네요.. 혜원님 아이디어가 도움이 됐습니다

[yeahdy]

🤔 시간복잡도 고려사항

• 알고리즘: dp
• 시간복잡도: n의 크기 10^4 > O(n^2)까지 가능
  • 조합O(2^N)으로 풀면 시간초과

💡 풀이 아이디어

• 점화식 규칙 찾기
  • n 을 만들기 위한 경우의 수
  • 1 부터 시작해서 1에서 찾을 수 있는 최대의 경우의 수를 찾고 다음으로 이동
  • 순열 중복 불가

    n=1 -> (1)
    n=2 -> (1 1) (2)
    n=3 -> (1 1 1) (1 2) (3)
    n=4 -> (1 1 1 1) (1 1 2) (1 3) (2 2)
    n=5 -> (1 1 1 1 1) (1 1 1 2) (1 2 2) (1 1 3) (2 3)

    이때 n 이 될 수 있는 각 경우의 마지막 수가 (ex. (1 1) 경우의 마지막 수는 1) 1 2 3 마다 각각 몇번 나오는지 갯수를 셌을 때, 이 갯수의 총합이 n이 될 수 있는 전체 방법의 수가 된다

N 마다 1 2 3 이 마지막으로 올 때의 각 갯수가 모두 저장 되어 있을 때 →DP N 의 전체 방법의 수를 아래 규칙으로 찾을 수 있다.

(N -1의 첫번째 갯수) +  (N-2의 첫번째 두번째 갯수) + (N-3의 첫번째 두번째 세번째 갯수)