분류 전체보기
-
백준 2186(문자판)전공/알고리즘 2020. 10. 25. 17:06
www.acmicpc.net/problem/2186 2186번: 문자판 첫째 줄에 N(1 ≤ N ≤ 100), M(1 ≤ M ≤ 100), K(1 ≤ K ≤ 5)가 주어진다. 다음 N개의 줄에는 M개의 알파벳 대문자가 주어지는데, 이는 N×M 크기의 문자판을 나타낸다. 다음 줄에는 1자 이상 80자 이하의 www.acmicpc.net 좀 전형적인 dp문제인것 같다. 그냥 점화식 자체가 그래프 + dp를 하게되면 top-down으로 기저조건 잘 넣고 [][][]이런식으로 몇번째 몇번째 칸을 몇번째 순서로 들어갈지 이런식으로 코드를 짜면 된다. 여기서 dp[i][j][num] 에는 마지막에서 (i,j)로 돌아왔을때 경우의 수가 저장된다. 설명이 이상한데 그냥 점화식을 쓰면 dp[i][j][num] += 모든..
-
백준 17845(수강 과목)전공/알고리즘 2020. 10. 25. 14:47
www.acmicpc.net/problem/17845 17845번: 수강 과목 첫줄에 서윤이의 최대 공부시간 N (1 ≤ N ≤ 10,000), 과목 수 K (1 ≤ K ≤ 1,000)이 공백을 사이에 두고 주어진다. 이후 K개의 줄에 중요도 I (1 ≤ I ≤ 100,000), 필요한 공부시간 (1 ≤ T ≤ 10,000)이 www.acmicpc.net xkdlaldfjtnl.tistory.com/122?category=903992 위 4190이랑 같은 문제이다. 정해진 범위가 있고, 하나하나 추가하면서 dp에 저장하는 문제. #include #include #include #include using namespace std; #define MAX 1005 int N, K; int dp[100001];..
-
백준 4190(Exact Change)전공/알고리즘 2020. 10. 25. 14:22
www.acmicpc.net/problem/4190 4190번: Exact Change The first line of input contains one integer specifying the number of test cases to follow. Each test case begins with a line containing an integer, the price in cents of the item you would like to buy. The price will not exceed 10 000 cents (i.e., \$100). www.acmicpc.net 진짜 한 스무번 제출한 문제 dp문제인데 이것 역시 나한테 엄청 도움이 되었던 문제인것 같다. 정해져 있는 금액이고, (0~MAX) 그 ..
-
백준 15487(A[j]-A[i]+A[l]-A[k])전공/알고리즘 2020. 10. 23. 12:24
www.acmicpc.net/problem/15487 15487번: A[j]-A[i]+A[l]-A[k] 크기가 N인 배열 A가 주어졌을 때, i < j < k < l을 만족하는 (i, j, k, l) 중에서 A[j]-A[i]+A[l]-A[k]의 최댓값을 구하는 프로그램을 작성하시오. www.acmicpc.net 구현이 진짜 어려웠던 문제 난 아직 인덱스 처리가 익숙치 않나보다. 생각정리만 좀 하면 바로 풀 수 있는 문제를 진짜 한 세네시간 헤맨듯? 단순하게 쪼개서 생각해주면 된다. 0~1까지 최대 0~j까지 최대를 저장하고, j+1 ~ N까지 최대를 하나하나 저장한 뒤에 인덱스를 잘 지지고 볶아서 j는 1에서 N-2까지 이동하면서 최대를 출력하면 된다. 지금 생각해보니 더 쉬운것 같기도? #include..
-
백준 11062(카드게임)전공/알고리즘 2020. 10. 22. 14:58
www.acmicpc.net/problem/11062 11062번: 카드 게임 근우와 명우는 재미있는 카드 게임을 하고 있다. N개의 카드가 일렬로 놓여 있다. 각 카드에는 점수가 적혀있다. 근우부터 시작하여 번갈아가면서 턴이 진행되는데 한 턴에는 가장 왼쪽에 있는 www.acmicpc.net 음 바로 직전에 푼 문제와 거의 동일한 문제이다. 그래도 얘기를 좀 해보면 dp를 어떻게 설정할지가 중요하다. 이것 역시 dp는 이중배열로 했고, dp를 배열하나로 값을 지정할 경우 그리디화 된다고 해야되나 그런 느낌이 든다. 1개를 뽑았을때의 최댓값 이런식으로 값을 구하려고 하면 그리디스럽다 그냥 기분이 실제로는 잘 모르겠다. 그래서 dp[i][j]에서 i, j까지 뽑았을때의 최댓값을 저장한다. 그러고 나서 내 ..
-
백준 1053(팰린드롬 공장)전공/알고리즘 2020. 10. 22. 13:09
www.acmicpc.net/problem/1053 1053번: 팰린드롬 공장 팰린드롬이란, 앞에서부터 읽었을 때와, 뒤에서부터 읽었을 때가 같은 문자열이다. 모든 문자열이 팰린드롬이 아니기 때문에 다음과 같은 4가지 연산으로 보통 문자열을 팰린드롬으로 만든다. www.acmicpc.net 진짜 대단하다 컴퓨터는 이 문제를 풀면서 컴퓨터는 진짜로 대단하다는 걸 느낀다. 사람이라면 조건을 다 따져서 하드코딩해야 하는 것을 컴퓨터는 그냥 다 해보면 된다. 그리고 dp는 더 아름답다. 이 문제는 dp이다. 태그에서 찾았기 때문에 dp인걸 알았지만 어떻게 풀어야 할지 감이 안 왔었다. 그러다가 그냥 하면 되지 않나 생각이 드는 순간 감이 왔다. 일단 우리는 팰린드롬인지 아닌지를 생각할 필요가 별로 없다. 이게 ..