PS(알고리즘 문제풀이) 관련 글/백준(Baekjoon)풀이 (43) 썸네일형 리스트형 백준 24025 : 돌의 정령 줄세우기 이 문제는 주어진 '시야점수' 조건에 맞추어 돌의 정령에 줄을 세우는 문제이다. 시야점수란 돌의 정령이 모두 오른쪽을 바라보고있을때, 해당 정령이 볼 수 있는 다른 정령의 수이다. 숫자를 통해 말하면 자신 오른쪽에오는 자신보다 큰 가장 왼쪽 수 까지의 거리 가 '시야 점수'이다. 이때 만약 자신의 오른쪽에 자신보다 큰 정령이 없는 경우 자신의 시아점수는 1e9 + 7이 된다.(사실상 MAX값) 문제에서 주어지는 조건의 수열을 arr이라 할때, arr[i]가 양수인 경우 자신의 시야점수가 arr[i] 이상이 되어야하고arr[i]가 음수인 경우 자신의 시야점수가 arr[i] 이하여야 한다. 이 문제는 간단한 방법으로 풀 수 있다.우선 문제의 조건에서는 이상, 이하만을 말하고 있음으로, 언제나 최대 혹은 최.. 백준 28121 : 산책과 쿼리 문제 개요주어진 그래프에서 시작점으로 돌아오는 경로의 길이가 10^{6} 이상인 t인 노드의 개수를 구하는 문제이다. 한 노드는 여러 번 방문 가능하며, 왕복 경로를 찾는 것이 핵심이다.풀이 아이디어그래프를 이분그래프로 변환노드 간의 관계를 짝수 시간 노드와 홀수 시간 노드로 나눈다. 노드 v_{0}는 짝수 시간에, v_{1}은 홀수 시간에 도달 가능한 노드를 의미한다.Union-Find(Disjoint Set Union)DSU를 사용해 연결된 노드 집합을 관리하며, 다음 두 가지 관계를 처리한다:짝수 노드와 홀수 노드의 연결짝수-홀수, 홀수-짝수 간선이 하나의 집합에 포함되도록 병합가능한 노드의 수 계산DSU 구조를 통해 특정 집합에서 짝수 시간 노드와 홀수 시간 노드의 개수를 합산하여 결과를 계산.. 백준 : 30392 K분 그래프 주어진 그래프에서 그래프의 Closed walk P에대해 P의 간선에 가중치의 합이 항 상K의 배수인지를 판별하는 문제이다.여기서 닫힌 보행(Close walk)란 시작점과 끝점이 같으며, 같은 정점과 간선을 여러 번 방문할 수 있는 경로를 말한다. 이 문제는 mod연산의 성질과 이분그래프의 접근을 통해 해결이 가능하다. 주어진 그래프에 임의의 한 점에서부터주어진 그래프에서 그래프의 Closed walk P에대해 P의 간선에 가중치의 합이 항 상K의 배수인지를 판별하는 문제이다. 여기서 닫힌 보행(Close walk)란 시작점과 끝점이 같으며, 같은 정점과 간선을 여러 번 방문할 수 있는 경로를 말한다. 이 문제는 mod연산의 성질과 이분그래프의 접근을 통해 해결이 가능하다. 이 문제를 “그래프 상에서.. 백준 25597 : 푸앙이 러닝머신 이번주 solved.ac 마라톤문제이다. 정지, 1m/s, 4m/s, 8m/s의 버튼 4개가 있는 러닝머신을 통해 T초에 정확히 X의 거리를 가려고 할 때 눌러야할 버튼의 최소횟수와, 버튼을 언제 눌러야하는지를 구해야하는 문제이다. 먼저, 정지버튼이 존재함으로 주어진 X의 거리를 최단시간안에 완주하고자할때의 8m/s, 4m/s, 1m/s가 각각 몇번씩 필요한지를 그리디하게 구할 수 있다.이때 8, 4, 1버튼의 필요횟수를 x, y, z라 할때8x + 4y + z = X이고 이때 x + y + z > T라면 불가능함으로 -1을 출력하면된다.만약 가능하다면, x, y, z를 8 -> 4 -> 1순으로 가능한 적은 버튼을 누르도록 버튼을 합쳐 최적의 해를 구해가면 된다. Code#include #include.. 백준 2228 : 구간 나누기 간단한 DP문제이다. Dp[i][j]를 "i개의 그룹으로 j까지 구간을 나누었을때 만들 수 있는 최댓값"으로 정의한 뒤에 풀면 쉽게 풀 수 있다.n범위가 100으로 작은 편이기에 3중 for문을 이용해도 된다.따라서,0~j - 2구간을 탐색하는 k를 이용하면 풀 수 있다.(0~k까지의 구간을 i - 1개로 나누었을 때 만들 수 있는 최댓값) + (k~j의 원소의 합)중 최댓값이Dp[i][j]의 값이다. 문제의 조건을 주의하자.나는 배열의 크기를 반대로 잡아서 한참을 고민했다. Code#include #include #include using namespace std;using ll = long long;int n, m;ll arr[110];ll dp[110][110], sum[110];int main().. 백준 33147 : k-정렬 shake 대회 1번문제이다.나는 이 문제를 푸는데 생각보다 오래걸렸다. 우선 이 문제를 푸는데 mod연산에 대해 알아야한다.a mod b = a % b라고 생각하면 편하다. 문제에서 구해야하는것은 주어진 수열을 K칸씩 옮겨, 오름차순으로 만들 수 있는가의 여부를 판단하는 것이다.이전 칸이 i일때, 이 수를 K칸옮기는 방법은 (i + K) mod n으로 옮기는것, 즉 범위를 벗어나면 n을 뺀다고 생각하면 편하다. 몇가지 데이터를 이용해 직접 해보면, 모든수가 Gcd(n, k)를 주기로 순환한다는것을 알 수 있다.나는 데이터를 실험해보는중, LCM(n, k)번을 반복하면 다시 제자리로 돌아온다는것을 알게되었고, 이에 착안하여 위의 풀이를 떠올렸다. 모든수가 Gcd(n, k)를 주기로 순환한다는 아이디어를 .. 백준 17353 : 하늘에서 떨어지는 1, 2, ..., R-L+1개의 별 수열이 주어지고, Q개의 쿼리가 주어졌을 때 해당 쿼리를 처리하는 문제이다.각 쿼리는 2개중 하나이며 처리해야하는 쿼리의 내용은 다음과 같다.1. L ~ R범위에 1 ~ (R - L + 1)의 등타수열을 더한다.2. X번째 값을 출력한다. 나는 이 문제를 레이지 프로퍼게이션을 이용하여 풀었다. 주어진 범위의 첫째항이 1이고 공차가 1인 등차수열을 더해가며, 규칙을 찾다보면 몇가지 규칙이 보이게된다.범위에서 연산이 겹치는 경우 첫째항과 공차는 서로 더해진다.예를 들어1, 1, 1, 1, 1 와 같은 배열이 존재하고, 이 배열에 1번 쿼리2번을 다음과같이 처리했을 때Q2 -> L = 1, R = 3Q2 -> L = 2, R = 3 [2, 3]범위를 생각해보면첫번째 쿼리를 처리했을때, 첫째항은 2, 공차는 1.. 25487 : 단순한 문제 (Large) 이 문제는 주어진 a, b, c의 값을 가지고 조건을 만족하는 경우의 수를 구하는 문제이다.조건은 다음과 같다.1 1 1 의 조건을 만족하는 (x, y, z)의 값이(x mod y) = (y mod z) = (z mod x)를 만족한다. 이 문제를 해결하기 위해선 간단한 정수론이 필요하다.우선 (x mod y) = (y mod z) = (z mod x) = k로 두자.이때, (x mod y) = k라면, k 결국 주어진 조건을 만족하기 위해선k 그리고 이를 이용하면(x mod y) = y와 동치이다.마찬가지로, (y mod z) y >= z(z mod x) z >= x 결국 x >= y >= z >= x임으로 이를 만족하는 순서쌍 (x, y, z)는 x == y == z인 경우밖에 없다.답은 min(.. 이전 1 2 3 4 ··· 6 다음 목록 더보기
