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

풀이

• 9084 번 문제와 동일한 문제

• ex)

  

• d[i] : i원을 만드는 경우의 수

  • 2원으로 i 만드는 경우의 수 + 3원으로 i 만드는 경우의 수 + 5원으로 i 만드는 경우의 수

• 목표금액 7원을 만드는 경우

  • 2원으로 만드는 경우 : 위 표와 같다

  • 3원으로 만드는 경우 : 이전 결과에 경우의 수를 더한다.

    • money가 6원 일 때

      • 2원 * 3개 (이전 결과)
      • 3원 * 2개

    • money가 7원 일 때

      • 2원 * 2개 + 3원 * 1개

• X 의 의미

  • 2원으로 1원을 만들 수 없다
  • 3원으로 1원, 2원을 만들 수 없다
  • 5원으로 1원, 2원, 3원, 4원을 만들 수 없다

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

풀이

• d[i]
  • i 수를 제곱수의 합으로 표현 할 수 있는 경우의 수
• 중복 문제 발생
  • 1
    • 1
    • d[1] = 1
  • 4
    • 1 + 1 + 1 + 1
    • 4
    • d[4] = 2
  • 5
    • 1의 제곱 + 4
      • d[4] = 2
    • 2의 제곱 + 1
      • d[1] = 1
    • d[5] = d[4] + d[1] = 3
    • 여기서 중복 문제가 발생
    • 사실, d[5] = 2
• 중복 해결이 관건

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

풀이

• d[i][j][k]
  • i라운드에서, A팀이 j 포인트, B팀이 k포인트 얻었을 때, 18라운드까지 한 확률의 합
• 경우의 수
  • i 라운드드에서
    • A팀 : 1골, B팀 : 0골
    • A팀 : 0골, B팀 : 1골
    • A팀 : 1골, B팀 : 1골
    • A팀 : 0골, B팀 : 0골

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

풀이

• ‘’가장 긴 증가하는 부분수열’’ 문제와 동일
• 처음에 계속 틀렸음
  • 이유 : j를 i-1 ~ 0 번째까지 비교해야하는데 1번째 까지만 비교했음

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

풀이

• 백트렉킹 문제
• 어렵다, 다시 풀어야함

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

틀린 풀이

• 각 페이지마다 접근해서 각 숫자가 몇개씩 있나 체크

• ex)

  • 1~12 페이지가 있으면
  • 1, 2, 3, 4,,,,12 차례로 접근
  • cnt[0] ~ cnt[9] 짜리 배열 ++
  • 10페이지 : cnt[1]++, cnt[0]++

• 이렇게 접근하면 시간 초과

• 규칙 필요

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

풀이

• 각 자리마다 쓰이는 개수를 구해서 합한다

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

중복을 고려하지 않고

• d[i]
  • d[i-2] * 2 + d[i-1]

중복을 고려하여

• 전체 타일 수 = A + 2B

  • A : 중복되지 않는 수
  • B : 중복되는 수

• 중복을 제거한 타일 수 = A + B = (A + 2B + A) / 2

• A 개수 구하기

  • i가 홀수인 경우

    • 가운데 2*1을 두고, 남은 좌우 채움
    • s[i] = d[i/2]

  • i가 짝수인 경우

    • s[i] = d[i/2-1] * 2 + d[i/2]
    • 가운데, 1*2를 주고, 남은 좌우 채움
      • d[i/2-1]
    • 가운데, 2*2를 주고, 남은 좌우 채움
      • d[i/2-1]
    • 반반 나눠서 채움
      • d[i/2]

결과

• 런타임 에러가 뜸

• 해결 : 배열 31로 고정

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

풀이

• 처음에 틀렸다고 나옴
  • 이유 : 반복문의 if-else 구문에서 else문에 걸렸을 때, 바로 출력하고 return
  • 해결 : break 걸고, 반복문 밖에서 정답 출력
• 100과의 차이는 계속해서 감소하거나 같음
• ex)
  • 100과의 차이가
  • 90 70 30 1 1 …
  • 인 경우가 있을 수 있으니
  • 현재 index에서의 차이가
  • 전 index에서의 차이보다 커지면
  • stop

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

틀린 풀이

• 어렵다
• 재귀 사용
• 문이 있는지 없는지 체크
  • 문이 없으면 옮기기
  • 문이 있으면 좌우 확인 -> 다시 문이 있는지 없는지 체크