PS/BOJ57 dp with 포함배제 원리 포함배제 원리를 이용하는 dp문제 2개를 풀어보자. 1. BOJ 14517 https://www.acmicpc.net/problem/14517 14517번: 팰린드롬 개수 구하기 (Large) 팰린드롬(palindrome)이란 앞에서부터 읽으나 뒤에서부터 읽으나 같은 단어를 말한다. 'aba'나 'a'와 같은 단어는 팰린드롬이며, 'abaccbcb'나 'anavolimilana'와 같은 단어는 팰린드롬이 아니다. 승수는 주 www.acmicpc.net [ 풀이 ] 문제를 잘 이해해야 한다. 부분수열이므로 연속된 팰린드롬일 필요가 없다. 맨처음과 끝에서 시작해서 좁혀가면서 갱신해주면 된다. dp[s][e]:=구간 [s,e]를 볼 때 팰린드롬의 총 개수라고 정의하면, 상태전이는 3가지가 있다. 1. s를 사.. 2022. 8. 1. 백준 11066 / C++ https://www.acmicpc.net/problem/11066 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net 0. 전체적인 접근 파일을 연속적으로 합쳐야 하는게 파일합치기3 문제와 다른 점이다. dp[i][j]를 i부터 j까지 합친 최솟값이라 하자. 연속적으로 합쳐야 하므로.. i tc; while (tc--) { int n; cin >> n; for (int i = 1; i > a[i]; psum[i] = psum[i - 1] + a[i]; } memset(dp, -1, sizeof(dp));.. 2022. 7. 21. 백준 6062 / C++ https://www.acmicpc.net/problem/6062 6062번: Mixed Up Cows Each of Farmer John's N (4 2022. 7. 21. 백준 1520 / C++ https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net [ 풀이 ] dp[i][j]를 (i,j)부터 출발할때 끝점에 도착하는 것의 개수라고 하자. 기저조건은 dp[n-1][m-1]=1이다. dp[i][j]=∑ 4방향 dp[x][y] 이다. 4방향중 높이조건을 위배하거나 칸을 벗어난다면 제외해주면 된다. 답은 dp[0][0]이 된다. [ 코드 ] #include using namespace std; int dx[] = { -1,1,0,0 }; int dy[].. 2022. 7. 21. 이전 1 ··· 8 9 10 11 12 13 14 15 다음