Go, Vantage point
가까운 곳을 걷지 않고 서는 먼 곳을 갈 수 없다.
Github | https://github.com/overnew/
Blog | https://everenew.tistory.com/
티스토리 뷰
문제
https://www.acmicpc.net/problem/1509
풀이
일단 이전 단계인 문제 팰린드롬?을 풀고 오자.
이전 문제에서 우리는 start에서 end까지 팰린드롬을 이루는지의 여부를 is_palin[start][end] 저장해 문제를 해결하였다.
이번 문제에서도 해당 저장 값을 그대로 이용하자.
첫 글자(1)에서 현재 위치 (i)까지의 팰리드롬 개수의 최솟값을 dp[i]에 저장하자.
i 번째 글자까지가 팰린드롬이지의 여부는 is_palin[1~i][i]를 확인해보면 된다.
is_palin[j+1][i]이 true인 경우
j+1~i까지를 하나의 팰린드롬으로 묶어 1개의 분할을 얻는다.
그리고 1~j까지의 팰리드롬 분할 개수의 최솟값을 저장하는 dp[j]값을 1과 더해
(j+1,i)를 팰린드롬 으로 묶을 때의 최솟값을 dp[j] +1로 얻을 수 있다.
이제 j를 0~i-1까지 순회하며 얻은 가장 작을 값이 dp[i]의 값이 된다.
따라서 dp[i] = min(dp[i], dp[j+1]+1) 이다.
참고로 문자열을 인덱스 1부터 시작하도록 변환하여
dp[0] = 0의 값을 미리 넣어두면
dp[2] = min(dp[2], dp[0]+1)과 같이 1~2를 하나의 팰린드롬으로 묶었을 때 이전의 글자가 더 없기 때문에, 계산이 용이해진다.
코드
'알고리즘 공부 > 백준' 카테고리의 다른 글
[백준] No.1931 - 회의실 배정 (C++) (0) | 2020.12.17 |
---|---|
[백준] No.2618 - 경찰차 (C++) (2) | 2020.12.12 |
[백준] No.1328 - 고층 빌딩 (C++) (0) | 2020.12.08 |
[백준] No.13398 - 연속합2 (C++) (0) | 2020.12.06 |
[백준] No.10942 - 팰린드롬? (C++) (0) | 2020.12.06 |