본문 바로가기

분류 전체보기140

[백준] 1793 - 타일링 https://www.acmicpc.net/problem/1793 1793번: 타일링 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 정수 n이 주어진다. www.acmicpc.net 2 x n 직사각형을 2 x 1 직사각형과 2 x 2 정사각형으로 채우는 문제이다. 간단히 생각해보면, 끝에 부분을 2 x 1로 채울 것인지 2 x 2로 채울 것인지에 대해 점화식이 탄생한다. 2 x 2로 채울 경우, 가로로 2 x 1직사각형을 2개 채울 수 있으므로 점화식은 다음과 같다. dp[i] = dp[i - 2] * 2(정사각형 1개, 가로 직사각형 2개) + dp[i - 1] 또한 이 문제는 cpp로 해결할 경우 큰 수 연산을 구현해야 한다. 큰 수 연산은 한 번 .. 2022. 9. 3.
[백준] 2228 - 구간 나누기 https://www.acmicpc.net/problem/2228 2228번: 구간 나누기 N(1 ≤ N ≤ 100)개의 수로 이루어진 1차원 배열이 있다. 이 배열에서 M(1 ≤ M ≤ ⌈(N/2)⌉)개의 구간을 선택해서, 구간에 속한 수들의 총 합이 최대가 되도록 하려 한다. 단, 다음의 조건들이 만족되 www.acmicpc.net dp[i][j] = 0 ~ i번째 수로 j개의 구간을 만들었을 때 최댓값으로 정의하여 top-down으로 해결했다. 이때 두가지 경우가 나온다. i번째 수를 j번째 구간에 포함시키지 않을 때 dp[i][j] = dp[i - 1][j] i번째 수를 j번째 구간에 포함시킬 때 이때는 j번째 구간이 어디서부터 어디까지인지 한번에 알지 못한다. 그래서 미리 구해둔 구간 합 배열을.. 2022. 9. 1.
[백준] 13302 - 리조트 https://www.acmicpc.net/problem/13302 13302번: 리조트 수영이는 여름방학을 맞이하여 많은 놀이 시설이 있는 KOI 리조트에 놀러가려고 한다. 리조트의 하루 이용권의 가격은 만원이다. 하지만 리조트의 규모는 상상을 초월하여 모든 시설을 충분히 www.acmicpc.net 이 문제는 처음에 쿠폰을 3장 이상 가질 수 없다고 생각해서 낭패를 보았다. 그래서 dp배열을 100 x 3으로 설정해서 제대로 된 답이 나오지 않았고, 이후에 dp[i][j] (i = 3) ret = min(ret, go(day + 1, coupon - 3)); } return dp[day][coupon] = ret; } int main() { cin >> n >> m; for (int i = 0; i .. 2022. 9. 1.
[백준] 2473 - 세 용액 https://www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 두 용액에서 업그레이드된 버전이다. 사실 그냥 for 한 번만 더 넣으면 되긴 하다. 미리 배열을 정렬 시키고 이중 for문으로 첫 번째, 두 번째 용액을 골라준다. 세 번째 용액까지 완전 탐색을 해버리면 TLE가 나기 때문에 정렬된 배열로 이분 탐색을 해준다. 이분 탐색의 기준은, 세 용액의 합이 0보다 크면 right = mid - 1 세 용액의 합이 0보다 작으면 lef.. 2022. 8. 26.
[백준] 1761 - 정점들의 거리 https://www.acmicpc.net/problem/1761 1761번: 정점들의 거리 첫째 줄에 노드의 개수 N이 입력되고 다음 N-1개의 줄에 트리 상에 연결된 두 점과 거리를 입력받는다. 그 다음 줄에 M이 주어지고, 다음 M개의 줄에 거리를 알고 싶은 노드 쌍이 한 줄에 한 쌍씩 www.acmicpc.net 문제를 보자마자 LCA(log)가 떠올랐다. 그런데 이 문제는 이웃한 정점 간의 거리가 주어지고, 임의의 두 정점 간의 거리를 구하는 문제이다. 두 가지 정도 방법이 존재하겠다. 루트 노드부터 모든 정점간의 거리를 dfs로 구하고, dis[a] + dis[b] - 2 * dis[LCA(a, b)]를 구하면 답이다. 두 정점부터 LCA를 찾아가며 거리를 더한다. 2번 먼저 코드로 보겠다. .. 2022. 8. 26.
[백준] 1493 - 박스 채우기 https://www.acmicpc.net/problem/1493 1493번: 박스 채우기 세준이는 length × width × height 크기의 박스를 가지고 있다. 그리고 세준이는 이 박스를 큐브를 이용해서 채우려고 한다. 큐브는 정육면체 모양이며, 한 변의 길이는 2의 제곱꼴이다. (1×1×1, 2×2×2, www.acmicpc.net 채워야 하는 박스는 직육면체이고, 채우는 큐브는 정육면체 형태이다. 그래서 항상 큰 것부터 넣는 것이 그리디한 방법이라고 할 수 있겠다. 그래서 큰 것을 넣으면 어떻게 되는가? 만약 L * W * H 크기(L > c >> b; a[c] = b; } cout 2022. 8. 26.
[백준] 1374 - 강의실 https://www.acmicpc.net/problem/1374 1374번: 강의실 첫째 줄에 강의의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 줄마다 세 개의 정수가 주어지는데, 순서대로 강의 번호, 강의 시작 시간, 강의 종료 시간을 의미한다. 강의 www.acmicpc.net 내가 제일 어려워하는 그리디 문제이다. 강의실을 가장 효율적으로 배정하는 방법은, 시작한 강의의 종료시간 이후에 가장 빨리 시작하는 강의를 배정하면 된다. 그래서 최소 힙에 현재 진행 중인 강의의 종료시간을 넣어주고 이제 시작해야 할 강의와 비교해서 맞바꾼다는 생각으로 구현하면 된다. #include #include #include using namespace std; pair ar.. 2022. 8. 26.
[백준] 19236 - 청소년 상어 https://www.acmicpc.net/problem/19236 19236번: 청소년 상어 첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 www.acmicpc.net 정말 이런 빡 구현 문제를 풀 때마다 수명이 줄어지는 것이 느껴진다. 이런 문제는 디버깅도 매우 어렵고 조금만 실수해도 답이 확 틀어진다. 이 문제를 다시 돌이켜보면, 그렇게 큰 실수가 아니었음에도 다시 풀면 한 번에 맞출 자신이 없다. 꾸준히 구현 문제를 풀어서 실수를 줄여나가야겠다. 먼저 물고기의 상태를 나타내는 구조체를 하나 선언하였다. 좌표, 방향, 생존여부이다. stru.. 2022. 8. 22.
[백준] 1083 - 소트 https://www.acmicpc.net/problem/1083 1083번: 소트 크기가 N인 배열 A가 있다. 배열에 있는 모든 수는 서로 다르다. 이 배열을 소트할 때, 연속된 두 개의 원소만 교환할 수 있다. 그리고, 교환은 많아봐야 S번 할 수 있다. 이때, 소트한 결과가 사전 www.acmicpc.net 수열이 하나 주어지고, 가능한 swap(a[i], a[i + 1]) 연산의 횟수가 주어질 때 사전 순으로 가장 후 순위 수열을 출력하는 문제이다. 처음에는 버블 소트처럼 수열을 계속 반복하며 무조건 앞에 있는 것이 크게 만들려고 했다. for (int j = 0; j < n - 1; j++) { if (a[j] < a[j + 1]) { swap(a[j], a[j + 1]); break; } }.. 2022. 8. 22.

티스토리툴바