USACO/Bronze (4) 썸네일형 리스트형 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의 배수가 되게끔 가져가면 항상 이기게 된다.반면 .. USACO 2023 December Contest - Bronze 풀이 & 후기 유사코문제셋으로 공부를 해본다해본다 하다가 드디어 처음으로 문제를 풀어보았다. 처음이니 가볍게 브론즈부터 시작해야지 라고 생각했는데 내 실력을 너무 과대 평가한것같다. 생각보다 엄청 어려웠다. 체감상 난이도는 Farmer John Actually Farms 못풀겠어서 중간에 에디토리얼을 봤다. A : Candy Cane Feast 구현자체는 쉽지만 시간복잡도때문에 쉽게 손이 가지않는 문제다. 하지만 나이브하게 처리해도 시간안에 돌아간다는 사실을 증명한다면 구현은 어렵지않다. 나이브한 방법에서는 O(N * M) 시간이 소요될 수 있으며, 이는 최대 4 * 10^10의 연산량으로 시간 초과가 발생할 수 있다. 따라서 이를 해결하기 위한 시간 최적화 방법을 고려해야 한다. 1. 각 소의 앞에 있는 소들이 자신.. 이전 1 다음