분류 전체보기(90)
-
BOJ 19568 : 직사각형
https://www.acmicpc.net/problem/19568 이 문제를 풀기 전, 약 팔기 문제를 먼저 풀고 오는 것을 추천한다. 약 팔기 아이디어를 2D로 확장시킨 문제이다. (15,15)를 중심으로 1, 15, 15^2, 15^3을 상하좌우로 한 줄에 펼쳐놓으면 50000 이상까지 찾을 수 있다. 코드
2021.11.16 -
BOJ 12935 : 트리와 경로의 길이 2
https://www.acmicpc.net/problem/12935 위 그림 같이 풀면 된다. 10000까지 돌려본 결과 노드의 갯수가 딱 500개로 맞추어지므로 이는 항상 성립한다. n,m+1을 브루트포스하여 구하고, 이를 저 그래프에 맞게 출력하면 된다. 딱 500개로 맞추어지는게 좀 신기한 문제였다. 코드
2021.11.16 -
BOJ 2315 : 가로등 끄기
https://www.acmicpc.net/problem/2315 dp로 풀 수 있다. dp[i][j][k] = i부터 j까지의 가로등을 모두 끄고 현재 위치가 (k==0 ? 앞 : 뒤)일때의 전력의 최솟값 cur : 현 위치, w : 시간당 전력소비량 dp[i-1][j][k] = min(dp[i-1][j][k], dp[i][j][k]+(cur-a[i-1].x)*w) (왼쪽으로 가서 끌 때) dp[i][j+1][k] = min(dp[i][j+1][k], dp[i][j][k]+(a[j+1].x-cur)*w) (오른쪽으로 가서 끌 때) w는 prefix sum을 통해 구할 수 있다. 이건 자력으로 풀었는데, 지금 보면 이걸 어떻게 자력으로 풀었나 싶을 정도로 어렵다고 생각한다. 코드
2021.11.16 -
BOJ 1126 : 같은 탑
https://www.acmicpc.net/problem/1126 dp로 풀 수 있다. dp[i][j] = i번째 블럭을 쓰고, 두 탑의 높이 차가 j일때 최대 높이 dp[i+1][j] = max(dp[i+1][j], dp[i][j]) (블럭을 사용 안할 때) dp[i+1][j+h] = max(dp[i+1][j+h], dp[i][j]+h) (블럭을 쌓아서 높이 차이를 크게 할 때) dp[i+1][|j-h|] = max(dp[i+1][|j-h|], dp[i][j]+max(j-h,0)) (블럭을 쌓아서 높이 차이를 작게 할 때) 어려워서 풀이를 보고 풀었는데 좀 많이 안해본 기술이 BOJ다른 분 코드에 있었다. -차피 dp테이블을 채울 때 첫 인자는 현재와 다음밖에 쓰지 않기 때문에 mod2 토글링을 해서 ..
2021.11.16 -
BOJ 9520 : NP-Hard
https://www.acmicpc.net/problem/9520 이 문제를 풀기 전 KOI 2003 경찰차 문제를 풀고 오는 것을 추천한다. 우리는 이 문제를 좀 바꾸어 생각해보면, 1부터 N까지의 자연수를 순서대로 앞 또는 뒤에 수를 추가하는 방식으로 수열을 만들고, 이를 순서로 해서 모든 도시를 방문할 때 비용의 최솟값을 구하는 문제이다. 이는 dp로 해결할 수 있다. dp[i][j] = 수열의 가장 왼쪽에 i가 있고, 가장 오른쪽에 j가 있을 때 최소 비용 dp[max(i,j)+1][j] = min(dp[max(i,j)+1][j], dp[i][j]+cost[i][max(i,j)+1]) dp[i][max(i,j)+1] = min(dp[i][max(i,j)+1], dp[i][j]+cost[j][max..
2021.11.16 -
BOJ 1201 : NMK
https://www.acmicpc.net/problem/1201 n+1m*k이면 안되는 경우이므로 걸러준다. k,k-1,k-2....1, 2k,2k-1,2k-2.....k+1,3k......min(n,mk).....(m-1)k+1 이런식의 수열을 만들면 된다. 증가 수열 : k, 2k, 3k....min(n,mk)으로 총 길이가 m이다. 감소 수열 : 각각 감소수열의 길이가 k개 혹은 그 이하이므로 최대 길이는 k이다. 아이디어가 좀 신기해서 재밌고 기억에 많이 남는 문제이다. 코드
2021.11.16