cdjs의 코딩 공부방

드디어 염원하던 블루 재등반 성공!!

어차피 다음 div2 풀면서 다시 떨굴 것 같긴 한데, 그래도 오프라인 개학 전까지 블루 재등반이라는 목표를 달성해서 신난다.

이번 난이도는 뭔가 Div3치고는 조금 어려웠던 느낌이었다. A번부터 뭔가 Div3답지 않았던거 같기도 하고...

저 B는 YES도 출력해야 되는지 모르고 왜 안되는지 낑낑대다가 C 풀고 나서야 알아챘다;;; 저것만 바로 풀었어도 +130도 가능했을텐데;

아무튼, 풀이나 하겠다.

https://codeforces.com/contest/1343/problem/A

A. Candies

Vova는 사탕을 매일마다 구매하며, 첫날에는 x개, 둘째날에는 2x개, 셋째날에는 4x개, ... k째날에는 2^(k-1)x개의 사탕을 구매한다.

이 때, 구매한 사탕 개수 n이 주어졌을 때, k>1 (k>=2)을 만족하는 x를 구하는 문제이다.

k는 2 이상인 아무 정수나 상관이 없으니까, k=2인 경우, k=3인 경우 ... 로 나누어서 생각해 보자.

k=2인 경우, 구매한 사탕은 x+2x = 3x이므로 n이 3의 배수인 경우, x=n/3이 된다.

k=3인 경우, 구매한 사탕은 x+2x+4x = 7x이므로 n이 7의 배수인 경우, x=n/7이 된다.

계속 이런 식으로 x의 계수를 늘려주면서, n%(x의 계수)==0인 경우 x = n/(x의 계수)를 출력해 주면 된다.

또한, 무조건 입력 n은 가능한 것으로 나오고, 2^31이 넘어가는 수치는 입력으로 들어오지 않으니, 반복문은 최대 31번까지만 돌리면 된다.

등비급수를 활용하여 2^n-1으로 식을 세워도 좋고, 그냥 계속 더해줘도 좋다. 어차피 뭘 선택하든 TLE는 안뜬다.

https://codeforces.com/contest/1343/problem/B

B. Balanced Array

사실상 A보다 쉬웠고, 그만큼 A보다 풀이자도 많았던 문제.

우선, n은 모두 짝수로 주어지며, n개의 배열 중 앞부분 n/2는 짝수, 뒷부분 n/2는 홀수이면서 앞부분과 뒷부분의 합이 동일한 원소 n개의 배열을 아무거나 출력해 주면 된다.

우선, n%4!=0인 경우에는, 자명하게 원소 n개의 배열을 만들 수 없다.

n이 4의 배수가 아니면, 앞부분의 원소와 뒷부분의 원소의 개수가 홀수가 되는데,

짝수+짝수+짝수=짝수, 홀수+홀수+홀수=홀수이므로 앞과 뒤의 합이 같을 수 없기 때문이다.

그렇다면 n%4==0인 경우에 어떻게 해주면 배열을 맞출 수 있을까?

여러 가지 방법들이 있겠지만, 본인은 그냥 가장 간단한 방법으로 풀었다.

예제에서 4 -> 2 4 1 5로 주어진 것을 활용해서,

n%4==0인 n이 주어졌을 때, 출력을 2, 4, 2+6*1, 4+6*1, 2+6*2, 4+6*2, .... , 1, 5, 1+6*1, 5+6*1, ...로 내게 했다.

즉, n==8인 경우에는 2 4 8 10 1 5 7 11이 나오고,

n==12인 경우에는 2 4 8 10 14 16 1 5 7 11 13 17이 나오고, ... 로 반복되는 것이다.

어차피 이렇게 하면 n이 4씩 더해질때 마다 앞부분과 뒷부분에 더해지는 값이 같이 때문에 무조건 앞부분과 뒷부분의 합이 같게 되고,

n<=200000인데 출력할 원소는 10^9보다 작기만 하면 되므로 출력 범위를 넘어설 일도 없다.

https://codeforces.com/contest/1343/problem/C

D번보다 훨씬 풀기 쉬웠던 문제.

배열 하나가 주어지고, 해당 배열의 부분배열 중 양수와 음수가 번갈아 나오는 최대 길이의 부분배열의 합의 최대를 구하는 문제이다.

문제를 좀 축약시키느라 말이 어려워 보이는데, 풀이는 그냥 간단하다.

우선 생각해야 할 점은, 배열 처음부터 끝까지 부호가 동일한 구간의 모든 원소를 하나씩은 모두 가져와야 한다.

그렇지 않으면 부분배열의 길이가 최대가 되지 않기 때문이다.

그리고, 그 배열의 합의 최대를 구하기 위해서는, 각 구간에서 가장 큰 수를 찾아서 ans에 더해주면, 해당 값이 정답이 된다.

이를 대충 알고리즘을 설명하면 다음과 같다.

1.배열 첫번째부터 시작해서, a[i]와 a[i+1]의 부호가 같은지 다른지 먼저 체크를 해 준다.

2-1.만약 부호가 같다면, maxnum값을 max(maxnum, a[i])로 갱신만 해 주고 넘기면 되고,

2-2.부호가 다르다면, maxnum값을 갱신해 준 뒤 -1234567890으로 초기화 해 준뒤, ans에 maxnum을 더해주면 된다.

그냥 이렇게 진행하는 코드를 구현하기만 하면 되는 문제였다.

팁으로, 앞부분과 뒷부분의 부호가 다른지 확인하기 위해서는 간단하게 (lld)(a[i]*a[i+1])<0을 체크해 주면 된다.

저런 식으로 체크할 때 주의해야 할 점은 a의 범위를 잘 생각하고, long long을 사용해야 한다는 것이다.

또한, -1 10^9 -1 10^9 .... 처럼 배열이 주어지면 ans값이 int 자료형을 넘길 수 있다는 것도 생각해 주어야 한다.

아마도 이 문제를 틀린 사람들은 자료형이 넘어가는 것을 체크를 안해줬거나, 구현 실력 미숙이 아닐까 하고 생각한다.

https://codeforces.com/contest/1343/problem/D

D. Constant Palindrome Sum

이번 contest에서 점수 떡상이냐 떡락이냐를 결정지었던 문제였다.

다행히 머리속에 풀이가 잘 떠올라 주어서 풀 수 있었지만, 못풀었다면 정말 슬플 뻔 했다.

배열의 길이 n과 k가 주어진다. 이 때 n은 짝수로만 주어진다.

그 다음에 길이가 n인 배열이 주어지는데, 이 배열의 원소들은 k보다 작거나 같다.

이 때 a[i]+a[n-i+1]의 값이 모두 같도록 배열을 바꿔주는 것이 목표이다.

(여기서 a[i]+a[n-i+1]는 그냥 팰린드롬 형식으로 1번째와 n번째, 2번째와 n-1번째... 의 합을 의미한다.)

이 때, 배열의 원소를 바꿀 때는 한번에 하나의 원소만을 바꿀 수 있고, 배열의 원소의 크기는 최대 k이다.

이 때 배열의 원소를 바꾸는 횟수의 최소값은 얼마인지를 구하는 문제였다.

우선, 한 팰린드롬 쌍(편의상 그냥 이렇게 부르겠다.)의 합을 다른 수로 바꾸기 위해선 최소 1번, 최대 2번의 변환이 필요하다.

가령 팰린드롬 쌍이 (1, 1)로 주어진 경우, 합을 k로 바꾸기 위해선 (1,k-1)로 한번, 2k로 바꾸기 위해선 (k,k)로 두 번 바꾸어 주어야 한다.

우선 가장 간단하게 생각할 만한 풀이는, 모든 팰린드롬 쌍의 합을 (k+1)로 바꾸어 주는 것이다.

한 쌍의 숫자 두개가 어떻게 주어지든, 두 숫자 중 단 한 번의 변환을 통해 해당 쌍의 합을 k+1로 만들어 줄 수 있기 때문이다.

(참고로, k+1은 쌍의 숫자로 k,k가 주어지든지, 1,1이 주어지든지에 상관없이 무조건 만들 수 있는 유일한 숫자이다.)

그렇다면, 우리는 정답은 무조건 n/2보다 작거나 같을 것이라는 것을 알 수 있다.

이제 들어오는 팰린드롬 쌍의 경우의 수를 생각해 보자.

만약 모든 팰린드롬 쌍의 합이 모두 다른 경우, 답을 어떻게 도출하면 될까?

이럴 경우엔 모든 팰린드롬 쌍의 합을 k+1로 바꾸는 경우(ans=n/2)와,

모든 팰린드롬 쌍의 합을 특정한 팰린드롬 쌍의 합으로 바꾸는 경우로 나누어 진다.

이 때, 후자가 답이 되기 위해서는 그 특정한 팰린드롬 쌍을 제외한 모든 팰린드롬 쌍에서 단 하나만의 원소를 바꾸어 주어야 하고, 이 때 정답은 n/2-1이 된다.

그렇다면 팰린드롬 쌍의 합들 중 중복하는 경우가 있다면 어떨까?

만약 모든 팰린드롬 쌍의 합을 가장 많이 중복된 팰린드롬 쌍의 합으로 바꾸는 경우를 생각해볼 수 있다.

하지만, 이렇게 했을 경우에도 답이 되기 위해선 한 쌍의 수 두개를 모두 바꾸는 경우가 중복된 팰린드롬 쌍보다 적어져야 한다.

즉, 이 문제에서 중요한 것은 "어떤 팰린드롬 쌍의 합을 특정한 수로 바꾸어 주기 위한 최소 연산 횟수"인 셈이다.

그렇다면 가장 처음 생각해 볼 만한 풀이는 이렇다.

우선, 모든 팰린드롬 쌍의 합을 찾는다.

그리고 나서, 각각의 팰린드롬 쌍의 합에 대하여, 모든 팰린드롬 쌍을 돌면서 해야 할 최소 변환 횟수를 계산한 뒤, 그 중 최소를 찾는다.

마지막으로, 그 최소값과 2/n값 중 작은 값을 정답으로 택한다.

하지만, 문제를 보면 알겠지만 팰린드롬 쌍은 최대 10만개까지 주어지고, 위 풀이는 O(n^2)이므로 시간 제한을 넘어가게 된다.

그래서 내가 생각한 풀이는, 다음과 같다.

우선 모든 팰린드롬 쌍을 돌며, 해당 팰린드롬 쌍의 합과 한 번 변환 시의 합의 최소 / 최대값을 구한다.

가령, 팰린드롬 쌍이 (3, 4)이고 k=7인 경우, 합 = 7, 합의 최소값은 (3,1)로 변환했을 경우의 4, 최대값은 (7,4)로 변환했을 경우의 11이다.

이렇게 주어진다면, 변환해야 할 합이 4이상 11이하이면 한번의 변환으로 맞출 수 있다는 뜻이고, 그렇지 않다면 두번의 변환을 거쳐야 한다는 것을 쉽게 알 수 있다.

그리고 이 최소값, 최대값을 저장해 준다.

본인같은 경우엔, map<int, int>에 key값으로 최소/최대값을 저장하고, value값으로는 최소일 경우 1, 최대일 경우 -1을 저장했다.

그리고 나서, 각각의 최소/최대 쌍에 대해, 다음과 같은 연산을 해 준다.

1. 오름차순으로 정렬된 팰린드롬 쌍의 합의 첫번째 원소를 골라서 저장한다.

2. sum+=map[key]로 sum을 구해 준다. (이 때, sum은 한번의 변환으로 해당 팰린드롬 쌍의 합을 만들 수 있는 쌍의 개수이다.)

3. 만약 현재 고른 팰린드롬 쌍의 합이 현재 key값보다 작다면, ans값을 갱신해 준다.

4. 반복이 끝나면, ans = min(ans, 2/n)으로 최종 답을 구해준다.

이 때, ans값은 다음과 같이 계산이 된다 :

ans = min(ans, sum - (해당 합을 만드는 쌍의 개수) + (n/2-sum)*2);

이렇게 해 주면, 훨씬 빠르게 ans값을 찾을 수 있다.

사실 본인이 코딩 실력이 좀 딸려서 비 효율적인 자료구조와 방법을 택했을지도 모르지만, 아무튼 뭐 풀렸으니 됐다 ^^

다른 사람의 코드를 보니 우선순위 큐를 사용할 수도 있고, 다양한 방법들이 있는 것 같다.

E,F는 그냥 읽자마자 "이건 내가 아직은 못푸는 문제다"라고 생각하고 때려쳤기 때문에 못풀었다.

언젠가 트리와 그래프 공부를 더 한 뒤에 풀어봐야겠다 ㅎㅎ