본문 바로가기

전체 글140

[백준] 2281 - 데스노트 https://www.acmicpc.net/problem/2281 2281번: 데스노트 첫째 줄에 n(1 ≤ n ≤ 1,000), m(1 ≤ m ≤ 1,000)이 주어진다. m은 노트의 가로 칸의 개수(폭, 너비)이다. 다음 n개의 줄에는 각 사람의 이름의 길이가 노트에 적어야 할 순서대로 주어진다. 각 길이는 m www.acmicpc.net 처음에 이분 탐색으로 해결하려고 했다가, 이분 탐색의 조건에 맞지 않아서 실패했고, 다음으로 다이나믹 프로그래밍으로 시도했다. dp로 풀기 위해서 배열을 다음과 같이 정의했다. dp[i] = i번째 사람의 이름까지 적었을 때, 제곱의 합의 최소 이렇게 되면 점화식은 굉장히 간단해진다. i 이전에 모든 경우의 수를 찾아서, 어디서 줄을 바꿀 건지만 결정하면 된다. f.. 2023. 8. 1.
[백준] 17828 - 문자열 화폐 https://www.acmicpc.net/problem/17828 17828번: 문자열 화폐 첫 번째 줄에 문자열의 길이 N(1 ≤ N ≤ 5,000,000)과, 문자열의 가치를 나타내는 정수 X(1 ≤ X ≤ 500,000,000)가 공백으로 구분되어 주어진다. www.acmicpc.net 사전 순으로 앞서는 문자열을 구하기 위해, 문자열의 앞부분부터 가능한 한 가장 작은 문자열을 이어 붙인다. 여기서 가능한 한 가장 작은 문자열이란? 예제 입출력 1을 살펴보자. 6 64 AAAIZZ A...... -> 화폐 가치 = 1, 남은 화폐 가치 = 63, 남은 화폐 수 = 5 AA.... -> 화폐 가치 = 2, 남은 화폐 가치 = 62, 남은 화폐 수 = 4 AAA... -> 화폐 가치 = 3, 남은 화.. 2023. 8. 1.
[백준] 2878 - 캔디캔디 https://www.acmicpc.net/problem/2878 2878번: 캔디캔디 첫째 줄에 M(1 ≤ M ≤ 2×109)와 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 친구들이 받고 싶어하는 사탕의 개수가 주어진다. 이 개수는 2×109보다 작으며, 친구들이 받고 싶어하는 www.acmicpc.net 분노의 합(제곱수의 합)을 최소화하기 위해서는 각 제곱수를 최소화해야 한다. 5^2 > 1^2 + 1^2 + 1^2 + 1^2 + 1^2 이런 식으로 제곱 수를 최대한 분할해야 최솟값을 구할 수 있다. 그렇다면 사탕의 개수를 오름차순으로 정렬한 후에 작은 것부터 나눠주면 된다고 생각할 수 있다. 하지만 이렇게 하면 다음과 같은 반례가 생긴다. 4 3 1 2 7 이 경우.. 2023. 8. 1.
[백준] 2463 - 비용 https://www.acmicpc.net/problem/2463 2463번: 비용 첫 번째 줄에 정점의 수 N (1< ≤ N ≤ 100,000)과 간선의 수 M (1 ≤ M ≤ 100,000)이 빈칸을 사이에 두고 주어진다. 다음 M개의 각 줄에 간선 하나에 대한 정보를 나타내는 세 개의 양의 정수 x,y,w가 빈칸 www.acmicpc.net 문제를 잘 읽어보고 다음을 생각해 보자. 가중치를 내림차순으로 보았을 때, 가중치 15의 간선은 Cost(3, 6)에서만 포함된다. 가중치 10의 간선은 Cost(3, 6), Cost(1, 2)에서만 포함된다. 가중치 6의 간선은 Cost(3, 6), Cost(1, 2), Cost(2, 6), Cost(2, 3), Cost(1, 3), Cost(1, 6)에서만 .. 2023. 7. 27.
[백준] 2291 - Sequence https://www.acmicpc.net/problem/2291 2291번: Sequence N, M, K가 주어질 때, A1 ≤ A2 ≤ ... ≤ AN 이고, A1 + A2 + ... + AN = M을 만족하는 수열 중 사전 순으로 K번째 수열을 출력한다. 모든 Ai는 자연수이다. 예를 들어, N = 4, M = 9, K = 3 이었으면, 1 1 1 6 1 1 2 www.acmicpc.net 길이가 최대 10, 합이 최대 220인 수열을 만들었을 때, k번째 비내림 차순 수열을 구하는 문제이다. 모든 경우의 수를 탐색하는 방법으로는 당연히 시간초과가 날 것이므로 다른 방법을 찾아야 한다. N = 4, M = 9 일 때 첫 번째 수가 1일 경우 뒤에 수열을 몇 가지 만들 수 있을까? 1 1 X X 1.. 2023. 7. 27.
[백준] 6597 - 트리 복구 https://www.acmicpc.net/problem/6597 6597번: 트리 복구 창영이는 바이너리 트리를 매우 좋아한다. 그가 가장 좋아하는 게임은 바이너리 트리를 만들고, 노드에 알파벳 대문자를 하나씩 쓰는 것이다. 같은 알파벳을 여러 노드에 쓰지 않는다. 아래는 www.acmicpc.net 트리의 순회 중, preorder와 inorder을 통해서 postorder를 구하는 문제이다. D / \ / \ B E / \ \ / \ \ A C G / / F 이 입력 1의 preorder와 inorder를 보면, preorder: DBACEGF inorder: ABCDEFG 인데, preorder의 각 정점과 inorder의 해당 정점의 위치를 잘 살펴보자. 먼저 최 상위 루트인 D를 보면 DBAC.. 2023. 7. 26.
[백준] 1132 - 합 https://www.acmicpc.net/problem/1132 1132번: 합 N개의 수가 주어진다. 이 숫자는 모두 자연수이고, 알파벳 A부터 J가 자리수를 대신해서 쓰여 있다. 이 알파벳은 모두 한 자리를 의미한다. 그리고, 각 자리수는 정확하게 알파벳 하나이다. 0으로 www.acmicpc.net 예제 입력 1을 함께 보자. 2 ABC BCA 이 문제의 모든 예제는 하나의 수식으로 표현할 수 있는데, 위의 예제를 수식으로 표현하면 다음과 같다. 100 * A + 10 * B + 1 * C + 100 * B + 10 * C + 1 * A = 101 * A + 110 * B + 11 * C 이렇게 수식을 만들면 당연히 B - A - C 순으로 큰 수가 배정되어야 한다고 볼 수 있다. 하지만 문제에서.. 2023. 7. 18.
[백준] 22116 - 창영이와 퇴근 https://www.acmicpc.net/problem/22116 22116번: 창영이와 퇴근 A1,1에서 AN,N까지, 경로상의 최대 경사의 최솟값을 출력한다. www.acmicpc.net N제한이 1000이므로, 정점의 최대 개수는 100만 개이고, 각 정점끼리 최대 4개의 다른 정점과 연결되어 있으므로 인접 리스트로 그래프를 나타낼 수 있다. (i,j) 정점 -> (i - 1) * n + j 번째 정점 이후 다익스트라를 돌려서 가장 비용이 적게 드는 경로로 (n , n)까지 찾아가면 된다. #include #include #include using namespace std; int n, a[1001][1001]; vector v; int x[4] = {0, 0, 1, -1}; int y[4] = .. 2023. 7. 7.
[백준] 1437 - 수 분해 https://www.acmicpc.net/problem/1437 1437번: 수 분해 첫째 줄에 음이 아닌 정수 N이 주어진다. N은 1,000,000보다 작거나 같다. www.acmicpc.net 이 문제를 처음 보고 당연히 2로 계속 분해하면 곱의 개수가 많아지고, 분해 곱이 커질 줄 알았다. 하지만 그렇지 않고, 3으로 분해했을 때가 가장 컸다. 다음과 같은 경우를 보자. 10 = 2 + 2 + 2 + 2 + 2 -> 2 * 2 * 2 * 2 * 2 = 32 10 = 3 + 3 + 2 * 2 -> 3 * 3 * 2 * 2 = 36 또한, 5 이상의 모든 수는 2와 3의 합으로 나타낼 수 있다. 주의해야 할 점은, 4의 최대 분해 곱은 4라는 것이다. (2 + 2 또는 4) #include usin.. 2023. 7. 7.

티스토리툴바