Study hard

www.acmicpc.net/problem/11066 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net [풀이] DP로 풀 수 있는 문제였다. DP[i][j] : i번째 장부터 j번째 장까지 어떤 순서로 합쳐야 최소비용이 나오는지(그 때의 최소비용) Sum[i] : 1장 ~ i장 비용 합 점화식 DP[i][[j] = min(DP[i][j], DP[i][k] + DP[k+1][j] + Sum[j] - Sum[i-1]) (여기서 Sum[j] - Sum[i-1]은 i~j번째 장을 최종으로 합칠 때 드는 비용,..

www.acmicpc.net/problem/15989 15989번: 1, 2, 3 더하기 4 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 4가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 합을 이루고 있는 수의 순서만 다른 것은 같은 것으로 친다. 1+1+1+1 2+1+1 (1+1+2, 1+2+1) 2+2 www.acmicpc.net [풀이] DP로 풀 수 있는 문제였다. 중복을 피하기 위해 오름차순으로만 더한다. DP[i][1]: 정수 i를 만들 때 1로 끝나는 경우 -> 그 이전에 1만 올 수 있다. DP[i][2]: 정수 i를 만들 때 2로 끝나는 경우 -> 그 이전에 1과 2가 올 수 있다. DP[i][3]: 정수 i를 만들 때 3으로 끝나는 경우 -> 그 이전에 1과 2..

acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net [풀이] 팰린드롬이란 수열이 거꾸로 했을 때도 같은 수열인 경우를 말한다. 가장 작은 단위의 수열(1개)부터 범위를 늘리면서 팰린드롬 여부를 판단하는 DP를 사용하였다. DP[i][j]: S가 i이고 E가 j일 때 팰린드롬인지 여부 DP[i][i] = 1 if Num[i]==Num[j] : DP[i][i+1]=1 DP[i][j] = DP[i+1][j-1] && Num[i] == Num[j] ※cin, cout을 사용하면 시간초과가 나므로 scanf, pri..

www.acmicpc.net/problem/15486 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net [풀이] 2020/09/14 - [백준/DP] - (c++)백준 14501번: 퇴사 (c++)백준 14501번: 퇴사 www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net [풀이] DP로 풀 수 있는 문제였다. DP[i]: i번째 날 상담하면 그 이후부터 최대로 받을.. nim..

www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net [풀이] DP로 풀 수 있는 문제였다. DP[i]: i번째 날 상담하면 그 이후부터 최대로 받을 수 있는 이익 상담이 끝나는 날이 N+1보다 커지면 무시한다. #include #include //max using namespace std; int N; int T[16]; int P[16]; int DP[16] = { 0, }; void solution() { int ans = 0; for (int i = N; i >= 1; i--) { //상담이 끝나는 날이 N+1보다 크면 if (i + T[i] > N + 1) continue; else { in..

www.acmicpc.net/problem/11060 11060번: 점프 점프 재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로 � www.acmicpc.net [풀이] DP로 풀 수 있는 문제! DP[i] : i번째 칸에서 최소 몇 번 점프해야 N번째 칸에 갈 수 있는지 주어진 칸이 한 칸일 경우, 한 번만 점프해서 N번째 칸에 갈 수 있는 경우, 점프할 수 없는 칸인 경우를 모두 신경써줘야 한다. #include #include //memset using namespace std; int N; int Maze[1001]; int DP[1001]; vo..