본문 바로가기

분류 전체보기

 (89)
백준 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연산의 성질과 이분그래프의 접근을 통해 해결이 가능하다. 이 문제를 “그래프 상에서..
USACO 2024 January Contest 1. Majority Opinion문제에서 주어진 N마리의 소들의 의견이 각각 다르다. 이때 인접하는 소들을 원하는 수만큼 묶어 그 그룹 전체를 그 그룹의 과반수의 의견으로 바꾼다. 그룹을 묶는 횟수에 제한이 없고, 최종적으로 모든 소를 하나의 의견으로 통일 시키면 되는 것임으로, 결국 3마리의 소를 묶었을 때, 해당 그룹에 2마리 이상의 소가 같은 의견이면 모든 의견을 통일시킬 수 있다.ex) aab, aba, baa ← 형태의 의견이 있다면 a로 통일이 가능하다.code#include #include #include #include using namespace std;int main(){ int i, j; int t; scanf("%d", &t); while(t--) { ..
USACO 2024 December Contest 1. Roundabout Rounding이 문제의 체인반올림은 1의자리에서부터 반올림을 해가면서 가장 높은자리까지 반올림을 하는 새로운 계산법이다. 이때, 체인반올림과 그냥 반올림을 한 수가 다른 1 ~ 주어진 N까지의 모든 수의 개수를 구하는 문제이다.간단히 45…55이 수부터 가장 높은자리에서의 반올림과 체인반올림이 달라지고, 50…00부터 같아짐으로 이 사이의 수를 모두구하면된다.만약 N이 50…00보다 크다면 50…00으로 N을 갱신후, 45…54를 빼주면 된다.code#include #include #include #include using namespace std;using ll = long long;ll P[11];int main(){ int t; scanf("%d", &t); ..
USACO 2024 February Contest 1. Palindrome Game이 문제는 두사람이 님게임을 할때, 두사람모두 펠린드롬(양쪽이 대칭인 수)만큼의 돌을 가져갈 수 있을 때의 승패를 판정하는 문제이다. 마지막 돌을 가져가는 사람이 이기며, 첫번째플레이어가 이기면 B, 두번째가 이기면 E를 출력하면 된다.이 문제는 BOJ의 돌게임 문제들과 같이 문제의 최적의 승패여부를 찾는 문제이다. 우선 입력범위부터, 반복문을 이용해 푸는것이 아니라는 힌트를 준다.이 문제의 핵심은 펠린드롬수 하나로만 10의 배수를 만들 수 없다는 것이다.즉, 주어진 돌의 수가 10으로 나누어떨어지면 첫번째 플레이어가 어떤수를 가져가든 1턴만에 10으로 나누어떨어지는 수를 만들 수 없음으로, 두번째플레이어가 남는 돌이 10의 배수가 되게끔 가져가면 항상 이기게 된다.반면 ..
백준 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()..

티스토리툴바