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

풀이

• 어렵다
• D[i][j][k]

1

i일, 지각 j번, 연속 결석 k번

• 오늘 출석

  • 전날에 출석, 지각, 결석 중에 하나
  • D[i][j][0] += D[i-1][j][k] (0 ≤ k ≤ 2)

• 오늘 지각

  • j 가 1
  • D[i][1][0] += d[i-1][0][k]

• 오늘 결석

  • k < 2
  • D[i][j][k+1] += D[i-1][j][k]

​

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

풀이

• dp[i][j]
  ​

    수열에서 i번째~j번째 수까지 합치는데 필요한 최소 비용
  

  ​ min(dp[i][k] + dp[k+1][j]) + (i~j 수열의 합) (i <= k < j) 일 때

    i _ _ _ k k+1 _ _ _ j     
  

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

풀이

• 런타임 에러가 계속 났음

• 원인

  • 자료형.
  • 문제의 입력으로 자연수 S(1≤S≤4,294,967,295)가 주어진다.
  • int의 범위를 넘기 때문에 런타임 에러가 계속 났음

• 해결

  • long형으로 입력 받음

• 쉬운 문제라도, 문제의 조건을 잘 확인해야함

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

풀이

• stack문제
• 스텍이 비었으면 push
• 스텍에 문자가 있으면, top문자 비교
• 같으면 pop
• 다르면 push
• 마지막에 stack이 비었으면 좋은 단어

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

풀이

• d[i]

    ikg을 담을 수 있는 최소 봉지 수
  

• ex) 6kg

    0 + 6 => 6을 3kg짜리 봉지 2개로 담을 수 있음 => d[6] = 2
  

  ​ 1 + 5 => d[1]== -1 => X
  ​ 2 + 4 => d[2]== -1 => X
  ​ 3 + 3 => d[6] = d[3] + d[3] = 1

• ex) 10kg

    0 + 10 => 10을 5kg짜리 봉지 2개로 담을 수 있음 => d[10] = 2 
  

  ​ 1 + 9 => d[1]== -1 => X
  ​ 2 + 8 => d[2]== -1 => X
  ​ 3 + 7 => d[7]== -1 => X
  ​ 4 + 6 => d[4]== -1 => X
  ​ 5 + 5 => d[5] == 1 => d[10] = d[5] + d[5] = 2

• 위와 같이, 앞 단계에서 사용된 값이 재사용된다. 따라서 DP

• 더 간결하게 어떻게 짤 수 있을까?

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

풀이

• 1~roomSize-1 까지 검사
• 펠린드 룸이 만들어 지는 경우가 있으면 그 뒤 펠린드 룸이 만들어지는 지점에

     result[i-1] +1
  

• 이미 넣어진 값이 있으면 최소값을 비교해서 대입

​

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

풀이

• ex) 1원, 5원, 10원이 있다. 만들어야하는 동전은 100원

• 1원을 이용해서

    d[1] : 1원을 만드는 경우의 수 => 1원, d[0] => 1
  

  ​ d[2] : 2원을 만드는 경우의 수 => 1원, d[1] => 1
  ​ d[3] : 3원을 만드는 경우의 수 => 1원, d[2] => 1
  ​ …
  ​ d[100] : 100원을 만드는 경우의 수 => 1원, d[99] => 1

• 5원을 이용해서

    d[5] : 5원을 만드는 경우의 수 => (1원, d[4]) + (5원, d[0]) => 1 + 1 => 2
  

  ​ d[6] : 6원을 만드는 경우의 수 => 1원, d[5] => 1
  ​ d[7] : 7원을 만드는 경우의 수 => 5원, d[2] => 1
  ​ …
  ​ d[9] : 9원을 만드는 경우의 수 => (1원,d[8]) + (5원, d[5])
  ​ …
  ​ d[100]

• 10원을 이용해서
  ​

    d[10] : 10원을 만드는 경우의 수 => (1원,d[9]) + (5원, d[5]) + (10원, d[0])
  

  ​ …
  ​ d[100]

• 위와 같이 전 단계에 나온 결과값을 재사용할 수 있다. 때문에 DP 문제이다.

​

​
​

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

풀이

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

​

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

풀이

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

​

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

풀이

• 쉬운 수학 문제

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

• 최소값 출력
  ​