![]()
A. Exciting Bets 문제 설명 + 풀이 a, b가 주어집니다. 이때 움직임 : (a, b를 1 증가 or a, b가 0이 아니면 1을 감소)해서 gcd(a, b)의 최대값과 gcd(a, b)를 만들 수 있는 최소의 움직임 횟수를 출력하시오. 만약 gcd(a, b)가 무한대라면 0 0을 출력 1. a == b라면 0 0을 출력 (gcd(a, b)가 무한대 일 때) 2. gcd(a, b)의 최대는 (a > b)일때 a - b가 최대가 된다. 3. 최소 움직임 : (a > b)일 때 b % (a - b)가 (a - b) / 2보다 작거나 같다면 움직임의 최소는 b % (a - b)이고, 크다면 (a - b) - b % (a - b)가 된다. 소스 코드(. cpp) #define _CRT_SECURE..
![]()
A. Odd Set 문제 설명 + 풀이 2n 개의 숫자가 주어진다. 이 수들 중 두 개씩 골라 n개의 페어를 만들고, 이 페어 안에 있는 두 수의 합이 모두 홀수가 될 수 있는지 확인하는 문제입니다. 간단합니다. 두 수의 합이 홀수가 되기 위해서는 반드시 홀수 + 짝수로 구성되어야 합니다. 따라서 2n개의 수들 중 n개가 홀수, n개가 짝수라면 yes, 아니면 모두 no입니다. 소스 코드(. cpp) #include using namespace std; typedef long long ll; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t; cin >> t; while (t--) { int n; cin >> n; int ..
A. Pretty Permutations 문제 및 풀이 수열 [1, 2, ..., n] 을 i번째 인덱스의 수가 i가 되지 않도록 재배치합니다. 단, 숫자의 움직임(기존 i번째 수 -> j번 위치 이동 시 | i - j | ) 의 합을 가장 작게 하도록 재배치한 결과를 출력합니다. 처음에 [n, 1, 2, ..., n-1] 이 정답인 줄 알았는데, 한 번 틀리고 알았네요,, 만약 n이 짝수라면 모든 수는 1칸만 이동해도 재배치가 가능합니다. 배열에서 순서대로 2*i, 2*(i+1) 을 서로 뒤집어주면 됩니다. 반면 n이 홀수라면 딱 한 수만 2칸을 이동해주면 됩니다. 문제에서 나온 n=3 테스트케이스처럼, 맨 앞에 1,2,3 을 3,1,2 로 바꿔주면 이제 n-3은 짝수이므로 짝수일 때와 동일하게 둘 씩..
![]()
A. Contest Start 문제 및 풀이 예외처리를 좀 해줘야하는.. 코드는 간단한 사칙연산 문제입니다. 그럼에도 불구하고.. 저도 끝까지 못맞추고, 1000점 tag가 달린 걸 보니 A번치고 어려운 문제라고 볼 수 있겠네요. 문제 요약을 하자면, n명의 사람이 있고 각 사람은 t 기간동안 대회에 참가합니다. 다만 각 사람이 대회를 시작하는 시점이 모두 다른데, 1 ~ n 명의 사람은 각각 x, 2x, ..., nx 에 대회를 시작하게 됩니다. 이 때, 어떤 사람 i가 대회가 끝났을 때 시점으로 대회를 진행중인 또는 대회를 지금 시작할 사람의 수를 "불만족" 이라고 합니다. 모든 참여자의 불만족 합을 구하는 문제입니다. 이 문제는 주어지는 변수 n, t, x 에 따라 몇 가지 경우의 수가 있습니다. ..
문제링크 codeforces.com/contest/1481 Dashboard - Codeforces Round #699 (Div. 2) - Codeforces codeforces.com A. Puzzle From the Future 문제 우주선으로 (0,0)에서 (px, py)로 이동하려고 한다. 우주선은 문자열 s에 입력된대로만 이동할 수 있고, 우주선이 문자열을 읽는 순서는 왼쪽에서 오른쪽으로 읽는다. 현재 좌표가 (x,y)이고, 읽어야하는 문자열의 위치가 s[i]일 때, 아래와 같은 규칙으로 이동한다고 한다. - s[i] == U이면 (x, y) -> (x, y+1)로 이동 - s[i] == D이면 (x, y) -> (x, y-1)로 이동 - s[i] == R이면 (x, y) -> (x+1, y)로..
![]()
문제 링크 codeforces.com/contest/1474 Dashboard - Codeforces Round #696 (Div. 2) - Codeforces codeforces.com A. Puzzle From the Future 문제 이진수 두 개를 가능한 한 크게 만드는 또 다른 이진수를 구하는 문제이다. 단, 연속된 수가 있으면 압축이 된다. 풀이 1 더보기 이 문제는 그리디하게 해결할 수 있습니다. 우선, 연속된 수에 대한 "아주 강렬한" 조건이 있기 때문에 직감적으로 이진수를 연속되게 만들면 안 될 것 같네요. 이미 이진수 하나가 주어져있기 때문에, 우리는 나머지 정답이 될 이진수는 연속되지 않도록 만들 수 있습니다. 또한 "가장 크게 만드는" 조건이 있으므로 최대한 2를 만들도록 노력해야겠..
![]()
문제 링크 codeforces.com/contest/1473 Dashboard - Educational Codeforces Round 102 (Rated for Div. 2) - Codeforces codeforces.com A. Replacing Elements 문제 양의 정수로 이루어진 수열 a가 주어질 때, 다음과 같은 작업을 할 수 있다. 서로 다른 인덱스 i, j, k를 고른 후, ai = aj + ak 로 바꿀 수 있다. 이 작업을 무한정 할 수 있다고 할 때, 수열 a의 모든 수를 d보다 작거나 같게 만들 수 있는가? 풀이 1 더보기 이 문제의 경우 두 가지 case일 때, 문제 조건을 만족시킬 수 있습니다. 1. 모든 수가 d보다 작거나 같을 때, 작업을 하지 않고 그대로 정답이 됩니다. ..
문제링크 atcoder.jp/contests/abc188 AtCoder Beginner Contest 188 - AtCoder AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp A - Three-Point shot 문제 : 농구 양팀의 점수가 주어지고(x,y x!=y), 지고있는 팀이 3점슛을 성공해 역전할 수 있는지 파악하는 문제 풀이 더보기 작은수에서 +3한수가 큰수보다 크면 되는 간단한 문제 코드 더보기 #define _USE_MATH_DEFINES #include using namespace std; using ll..
문제 링크 atcoder.jp/contests/arc111 A. Simple Math 2 문제 정수 N, M이 주어졌을 때 (|10^N / M|) % M 값을 구하는 문제입니다. 1 bag[i]; } for(int i=0;i> now[i]; now[i]--; temp[now[i]] = i; } sort(v.begin(),v.end()); vector ans; for(auto& i : v){ int& weight = i.first; int& idx = i.second; if(now[idx]==idx) continue; int dest = temp[idx]; if(person[idx]
문제 링크 codeforces.com/contest/1467 A. Wizard of Orz 문제 0~9까지 표현이 가능한 디지털 패널이 n개가 있다고 한다. 이 패널은 매초 1씩 증가하다가 9가 된 다음 1초 후에는 0으로 다시 표기된다. 이 패널을 멈추면 숫자가 일시정지가 되는데, 만약 패널이 일시정지가 되면 인접한 패널도 1초 뒤에 일시 정지가 되고, 그 일시 정지된 패널의 인접한 패널도 1초 뒤 일시 정지가 되고, ... 이 과정을 반복하여 패널들이 전부 멈출 때까지 반복이 된다고 한다. 디지털 패널을 딱 한 개만 선택하여 멈추게 할 수 있을 때, 패널이 표현할 수 있는 가장 큰 수를 출력하시오. 모든 패널은 전부 0에서부터 시작한다. 풀이 1 더보기 숫자를 0~9중 하나를 선택하는 것인데, 최대 ..
![]()
문제 링크 codeforces.com/contest/1471 A. Strange Partition 문제 n개의 정수 배열 a와 정수 x가 주어진다. 원하는 만큼 배열 안에 인접한 원소 두 개를 합쳐 하나로 만들 수 있다. 만약 이 작업을 하면 배열의 원소는 -1씩 줄어든다. 배열의 아름다움이란 배열의 각 원소를 주어진 정수 x로 나눈 후, 올림 한 값들을 더하여 나타내는데, 적당히 작업을 하여, 배열의 아름다움의 최소값과 최댓값을 나타내라. 풀이 1 더보기 나누고 몫을 올림 한다는 것은 원소가 많을 때 이득입니다. 만약 배열 내 원소 k가 있다고 하면, k는 두 가지 경우로 나뉩니다. 1) k가 x로 나누어 떨어지는 경우 : 이 경우 합치나 더하나 차이가 없습니다. 2) k가 x로 나누어 떨어지지 않는 ..
![]()
문제 링크 codeforces.com/contest/1472 A. Cards for Friends 문제 n명의 친구들에게 w x h 크기의 종이를 잘라 나누어 주고자 한다. 자르는 데에는 두 가지 규칙이 있다. w가 짝수일 때, 종이는 반으로 잘라 (w/2) x h 크기 종이 2장으로 만들 수 있다. h가 짝수일 때, 종이는 반으로 잘라 w x (h / 2) 크기 종이 2장으로 만들 수 있다. 주어진 w x h 크기 종이를 적당히 잘라 최소 n 조각을 만들 수 있는가? 풀이1 더보기 w, h 는 반드시 "짝수" 여야 종이의 개수를 늘릴 수 있다. 여기서 종이는 정확히 x 조각을 맞출 필요가 없기 때문에, 최대한 늘이는 방향으로 생각하자. 따라서, 종이의 최대 개수는 w, h 를 각각 "더 이상 짝수가 아..
