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

풀이

• 수학문제
• 오일러 회로 공부 필요
• 어렵다

​

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

풀이

• 점화식을 세워서 DP로 풀지 않음
• i번째 라운드에 i번째 방이 열려있는지 체크
• 열려있으면 닫고, 닫혀 있으면 열음
• 점화식을 세워서 어떻게 풀까??

​

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

풀이

• 쉬운 수학 문제

• (x, y)에서 상 하 좌 우로 얼만큼 떨어져있는지 계산

• 최소값 출력
  ​

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

풀이

• 완전 순열의 개념을 알아야함

    완전 순열 : n명의 사람이 자신의 모자를 벗어두었다가, 
  

  ​ 다시 쓰는데 모든 사람이 자기의 것이 아닌 모자를 쓰는 경우의 수

• d[i]

    i 명이 선물을 나누는 경우의 수
  

• a1 a2 a4 a4 …. aj … ai

• aj가 i 선물을, ai가 j 선물을 가지는 경우

    나머지 i-2 명이 선물을 나눠 가지면 된다 => d[i-2]
  

  ​ 그리고 aj는 ai를 제외한 명 수중 한 명 이므로 i-1

• aj가 i 선물을 가지고, ai가 j 선물으 가지지 않는 경우

    aj를 제외한 나머지 i-1명이 선물을 나눠 가지면 된다. => d[i-1]
  

  ​ 그리고 aj는 ai를 제외한 명 수중 한 명 이므로 i-1

• 그런데, 계속해서 런타임 에러가 발생했음

  • 문제

      d[2]를 초기화할 때, 반복문 안에서 조건을 걸어서 하지 않고,
    

    ​ 반복문 밖에서 초기화하면 런타임 에러가 뜸.
  • 해결

      반복문 안에서 초기화
    

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

풀이

• 풀어본 DP 문제 중 제일 어려움

• d[i, j]

    a[i..j] 의 부분 KOI 유전자 들 중 가장 긴 것의 길이
  

  ​

1. d[i, j] = 2

   • a[i..j] == “at”
   • a[i..j] == “gc”

2. d[i, j] = d[i+1, j-1] + 2

   • a[i]==”a” , a[j]=”t”
   • a[i]==”g” , a[j]=”c”

3. d[i, j] = d[i, k] + d[k+1, j]

- a[i...k] 의 부분 KOI 유전자 들 중 가장 긴 것의 길이 => d[i, k]

- a[k+1...j] 의 부분 KOI 유전자 들 중 가장 긴 것의 길이 => d[i, k]