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 문제이다.

​

​
​