목록2025/03/14 (1)

공부 흔적남기기

[JAVA] 백준 1509 팰린드롬 분할

DP 개념이 2개나 들어간 쉽지 않은 문제다.. 분할의 개수의 최솟값을 구하기 위해서는 모든 구간을 다 탐색하면서 펠린드롬인지 아닌지를 확인해야한다.pal[i][j[는 i~j 구간이 펠린드롬인지 여부를 저장하는 배열이다. pal[i[j]를 구할때 DP 없이 그냥 풀면 O(n^3)이 나온다 이렇게 해도 운이 좋았는지 Pass는 되었다.모든 구간을 탐색하는 코드이다.for(int i =0; i 이를 개선하기 위해 DP를 사용하는데모든 길이가 1인 문자는 펠린드롬, 뒤와 같은 값을 가진 구간은 펠린드롬일 것이고구간 i~j가 만약 펠린드롬이라면 i-1의 문자열과 j+1의 문자열이 같다면 i-1~j+1도 펠린드롬일 것이다.이 개념을 통해 DP를 구현한다.for(int i=0; i구간의 길이가 3인것 구간의 길이가..
코테/백준 2025. 3. 14. 20:37
이전 Prev 1 Next 다음