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

틀린 풀이

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

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

풀이

• 금메달, 은메달, 동메달 개수를 비교하여 정렬
• 등수 매기기에서 막혔음

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

틀린 풀이

• 계속 런타임 에러

• dp가 아니라, 수학적으로 풀었음

• 팩토리얼로 풀었음

  맞는 풀이

• d[i]

  • 길이가 i 일때, 만들 수 있는 수열의 개수
  • d[i-2] + d[i-1]

• 길이가 i인 수에는

  • 길이가 i-1인 수에
  • 00을 붙이거나
  • 1을 붙여서 만들 수 있다.
  • 하지만 00은 길이가 2 이기때문에, 붙일 수 없다.

• 따라서

  • i-2번째에 00을 붙이거나
  • i-1번째에 1을 붙인다

• 여기서 문제,

  • i-2번쨰에 11을 붙여서 만들 수 있지 않나?
  • 중복의 문제가 발생한다

• 따라서,

  • i-2번째 수열에, 00을 맨 뒤에 붙이고
  • i-1번째 수열에, 1을 맨 앞에 붙인다