전체 글 (90) 썸네일형 리스트형 백준 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(.. 백준 2141 : 우체국 각 사람까지의 거리의 합이 최소가 되는 우체국의 위치를 구해야 하는 문제이다.오늘 재체점에 갑자기 틀렸습니다. 가 떠서 급히 다시 푼 문제이다. 우체국이 설치될 위치는 전체 인구의 중앙이 되는 지점입니다. 이는 총 인구의 절반 지점에 해당하는 위치를 의미한다. 즉, 인구의 합을 2로 나눈 값에 해당하는 누적 인구를 찾아서 그 위치를 결정하면 된다. #include #include #include using namespace std;using ll = long long;int n;vector > vec;int main() { int i, j; scanf("%d", &n); ll ans = 0; for(i=0;i= res) { printf("%d", vec[i].fi.. 백준 26091 : 현대모비스 소프트웨어 아카데미 최대한 많은 팀을 만들되, 각 팀의 능력치 합이 최소값 M 이상이 되도록하는 문제이다. 투 포인터를 이용하면 간단하게 풀린다.로직은 다음과 같다.두 개의 포인터 low와 high를 사용하여 배열의 양 끝에서부터 탐색을 시작한다. - low 포인터는 배열의 시작에서, high 포인터는 배열의 끝에서 시작한다. - 현재 low와 high가 가리키는 두 원소의 합이 m 이상이면, 해당 팀을 구성할 수 있으므로 팀의 수를 증가시키고 포인터를 이동시킨다. - 현재 합이 m 미만이면, low 포인터를 오른쪽으로 이동시켜 합을 증가시킬 기회를 만든다. - 이 과정을 low 포인터가 high 포인터와 같아지거나 넘을 때까지 반복한다. #include #include using namespace std;int n, m;.. 백준 17359 : 전구 길만 걷자 주어진 전구묶음을 배열해 가장 인접한 두 전구의 상태가 다른 부분이 가장적도록 하는 문제이다.주어지는 전구묶음의 수가 10이하로 적음으로 O(N!)의 풀이를 생각할 수 있다. 먼저 주어진 전구의 묶음안에서 인접한 두 전구의 상태가 다른 부분이 몇개인지 찾는다. 그 후 1~N으로 순열을 만들어 해당 idx를 갖는 전구의 묶음을 순서대로 배열한다.이때 묶음과 묶음 경계에 있는 두 전구의 상태만 비교해주면된다. (각 묶음 안에 있는 인접한 상태가다른 전구는 이미 처리했기 때문) 즉 백트래킹을 이용하여 쉽게 풀 수 있는 문제이다. #include #include #include #include using namespace std;int n;string s[10];int ch[10];int ans = 2e9;ve.. 백준 15991 : 1, 2, 3 더하기 6 주어진 정수 N을 1, 2, 3의 합으로 나타내는 경우의수를 구하는 문제이다. 단, 합은 대칭을 이루어야 한다. DP 문제는 의외로 간단하다. 양쪽을 1, 2, 3으로 감싸는 방식을 생각하면 편하다. 예를 들어 dp[8]을 구할 때는 1 + 6을 구하는 방법 + 1, 2 + 4를 구하는 방법 + 2, 3 + 2를 구하는 방법 + 3으로 접근할 수 있다. 이를 바탕으로 점화식은 dp[i] = dp[i - 2] + dp[i - 4] + dp[i - 6]으로 세울 수 있다. 이 방식으로 문제를 해결할 수 있지만, 초기값을 6까지 설정해야 해서 다소 번거로울 수 있다. #include #include #include using namespace std;#define MOD 1000000009;int dp[100.. 이전 1 2 3 4 5 ··· 12 다음 목록 더보기
