DP2

• 

  [백준 Java] 10942 팰린드롬? 자바 10942 팰린드롬 dp https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 시간제한이 0.5초이고 메모리 제한이 커서 dp를 이용해서 저장해 두고 테스트 케이스에 대해서 계산된 값을 출력해야겠다고 생각했다. dp 테이블에는 팰린드롬이라면 1을 저장하고 아니면 0을 저장하였다. 포인트라고 생각한 아이디어는 i ~ j 까지가 팰린드롬인지를 확인하기 위해서 input[ i ]와 input[ j ]를 비교하고 i+1과 j-1까지가 팰린드롬 인지를 확인하면 된다. 예를 들어 만약 테스트 .. 알고리즘 2022. 10. 13.

• [백준]9465_스티커_dp [문제 링크] https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net [생각 흐름] dp 방법으로 해결하였다 선택할 수 있는 방법이 (1번 줄, 2번 줄) OX, XO, XX 세 가지를 가질 수 있으므로 (O는 스티커가 있다, X는 스티커가 없는 경우) 각 경우에 맞춰서 초기값을 계산하였다. 그리고 아래의 코드와 같이 ox-> xx , ox->xo, xx-> ox, xx->xo, xx->xx , xo->ox , xo->xx로 7가지의 경우로.. 알고리즘 2022. 9. 25.