https://codeforces.com/contest/1561/problem/A
Codeforces Round #740 (Div. 2, based on VK Cup 2021 - Final (Engine))

A. Simply Strange Sort

문제 요약

조금 이상한 정렬..

n개의 원소를 가지고있는 배열 a(n개의 원소를 가진 배열, n: 홀수)이 주어진다.
배열 a를 오름차순으로 정렬한다.

알고리즘: f(i)를 수행한다.
i는 (1 <= i <= n-1)사이로 수행되고, 각 다음과 같은 알고리즘을 사용한다 :
만약 **a_i > a_i+1**이면, **a_i 와 a_i+1의 값을 변경한다.

알고리즘은 반복으로 구성되고, 숫자 1부터 시작한다. i번째 반복일 때, 다음과 같은 알고리즘을 수행한다

• 만약 i가 홀수이면: f(1), f(3),…,f(n-2);를 호출
• 만약 i가 짝수이면: f(2), f(4),…,f(n-1);를 호출

배열이 오름차순으로 정렬될 때까지 반복한다.

몇번의 반복을 해야 오름차순으로 정렬되는지 구하는 문제…

피드백

Input

1-st line : Testcase (1 <= t <= 100)
각 Testcase 마다
1-st line : 1개의 정수 (1 <= n <= 1000, n: 홀수)
2-nd line : n개의 정수 a₁, a₂…,a_n (1 <= a_i <= n)

모든 테스트케이스의 n의 합이 999를 넘지 않는다.

Output

각 Testcase 마다
최초로 오름차순으로 정렬이 되는 최소 반복 횟수를 출력

이미 정렬이 되어있다면, 0을 출력

문제 풀이

그냥 무시정으로 반복해도 해결할 수 있는 문제이다. 알고리즘도 다 알려주고 위에서 시키는대로 코드를 짜기만 하면 되는 문제

Attr 1 (Wrong answer on pretest 2)

처음에는 checkSorted라는 변수를 하나 만들어서 반복문 안에서 변경되는 점이 있으면 checkSorted를 꺼주고, checkSorted가 꺼지지 않으면 정렬이 된것으로 보고 반복문을 탈출시켜주는 코드였다.

에러가 떴다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

#include <iostream>
 
using namespace std;
 
 
int main(void) {
    int TestCase = 0;
    cin >> TestCase;
    while (TestCase --)
    {
        int result = 0;
        int n, arr[1001];
        cin >> n;
        arr[0] = 0;
        for(int i = 1; i <= n; i++) {
            cin >> arr[i];
        }
        while(true) {
            result ++;
            int checkSorted = true;
            for(int i = (result%2==0?2:1); i < n; i+=2) {
                if(arr[i] > arr[i+1]) {
                    //cout << "exchange " << arr[i] << " and " << arr[i+1] << endl;
                    int temp = arr[i];
                    arr[i] = arr[i+1];
                    arr[i+1] = temp;
                    checkSorted = false;
                }
                if(arr[i-1] > arr[i]) checkSorted = false;
            }
            if(checkSorted) break;
        }
        
        cout << result - 1 << endl;
    }
    
    return 0;
}

Attr 2 (Accepted!)

에러가 날만한 테스트 케이스를 하나씩 넣어봤는데 바로 발견할 수 있었다.

1
2

5
1 2 3 5 4

위의 케이스를 넣었을때, 확인이 되지않고 0으로 출력이 되었다.
바로 해결할 수 있는 문제였는데, 햇갈려서 알고리즘을 다시 짜는 수준까지 가버렸다.

시간이 더 걸리더라도 그냥 배열이 정렬되었는지 미리 확인을 하는 코드를 추가했는데, 시간제한이 넉넉하다보니 문제없이 잘 작동하였었다.

바로 해결하지 못한 이유는 위 케이스의 답이 2가아닌 1이라 생각하고 삽질하고 있었다…

최종 해설

위의 해설이랑 똑같이 만들었다.

n을 먼저받고, 문제에서 1부터 시작했기 때문에 햇갈리지 않기 위해서 배열의 0은 0으로 채워주고 1부터 입력값을 받아주었다. (1~`n`)

그다음 정렬이 될 때까지 무한반복을 해주는데, 먼저 배열이 정렬되었는지 확인을 해준다. 단순히 for문으로 반복하면서 비교를 해주었다.

정렬이 되지않았으면 result값을 1 더해주고 문제에 나온 알고리즘을 수행해준다.

이렇게 반복하면 어렵지 않게 답을 구할 수 있다.

최종 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

#include <iostream>
 
using namespace std;
 
 
 
int main(void) {
    int TestCase = 0;
    cin >> TestCase;
    while (TestCase --)
    {
        int result = 0;
        int n, arr[1001];
        cin >> n;
        arr[0] = 0;
        for(int i = 1; i <= n; i++) {
            cin >> arr[i];
        }
        while(true) {
            //check if array sorted
            int i = 1;
            for(i; i < n; i++) 
                if(arr[i] > arr[i+1])
                    break;
            if(i == n) break;
 
            result ++;
            for(int i = (result%2==0?2:1); i < n; i+=2) {
                if(arr[i] > arr[i+1]) {
                    //cout << "exchange " << arr[i] << " and " << arr[i+1] << endl;
                    int temp = arr[i];
                    arr[i] = arr[i+1];
                    arr[i+1] = temp;
                }
            }
            
        }
        
        cout << result << endl;
    }
    
    return 0;
}

느낀점

알람은 미리미리 맞춰놓자.
정신좀 차리자.

https://codeforces.com/contest/1560/problem/D
Codeforces Round #739 (Div. 3)

D. Make a Power of Two

문제 요약

2의 제곱으로 만들어라.

정수 n이 주어지고, 다음과 같은 행동을 할 수 있다.

• 임의의 숫자 하나를 지울 수 있다 (만약 숫자가 하나밖에 남지 않았으면 “empty”가 된다)
• 오른쪽에 숫자 하나를 놓을 수 있다.

가장 왼쪽에 0이 있을 때, 0은 지워지지 않는다.
예시) 301에서 3을 빼면, 1이 아닌 01이 된다

최소한의 행동만 하여 n을 2의 제곱으로 만들어라.

피드백

Input

1-st line : Testcase (1 <= t <= 10⁴)
각 Testcase 마다
t-th line : 1개의 정수 (1 <= n <= 10⁹)

Output

각 Testcase 마다
1개의 정수 m : 2의 제곱으로 만드는 최소 비용

문제 풀이

처음엔 햇갈렸지만, 결국 string을 사용하여 노가다로 풀 수 있는 문제라는 사실을 깨닳았다.

하나의 문자를 구현하기 위해서는 구현할 문자와 비교해가면서 필요없는 숫자는 빼고, 필요한 숫자만 마지막에 더해주면 쉽게 구현을 할 수 있다.(비용은 언제나 최소비용이 든다)

또한 n의 최대 범위가 10의 9승이기 때문에, 아무리 비용이 많이 들어도 9 이상으로는 들지 않을 것이다.
10의 9승 이하에서 모든 값을 지우고 1만 추가하면 최대 9의 비용이 나온다

처음엔 long long int의 최대 범위를 10의 19승까지 했지만, 잘못된 선택이였다.

long long int의 범위를 잘못 알고 있었었다. 이부분에서 시간을 많이 잡아먹었다
결국 long long int의 범위 문제였고, 범위를 10의 18승으로 줄여 문제를 해결했다.

최종 해설

먼저 간단한 예외(n이 이미 2의 제곱일때)는 미리 검사하고 걸러냈다.

만약 그렇지 않으면, n을 string으로 바꿔서 시작한다.

그 뒤로 2의 제곱을 계속해서 비교해 가면서 최소비용을 계산을 한다.
만약 비용이 1이 나오면, 1보다 작은 비용은 나오지 않기 때문에 검사를 종료하였다.

검사는 n의 digit들을 하나씩 돌아가면서 구현할 숫자와 비교를 한다.
n과 다른 숫자가 있으면 해당 digit를 제거하고, n의 탐색이 먼저 끝나면 남은 digit들을 추가해주면 구현이 완료된다.

n의 최대값은 10⁹이므로 가장 큰 최소 비용은 9가 된다.
10의 9승 이하에서 모든 값을 지우고 1만 추가하면 최대 9의 비용이 나온다
그러므로 +-를 계산하여 구현해볼 최대의 2의 제곱수는 10¹⁸ 까지 확인을 해 주었다.

최종 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

#include <iostream>
#include <algorithm>
#include <math.h>
#include <string>
 
using namespace std;
 
bool CheckPow(int a) {
    while(a > 1) {
        if(a % 2) return false;
        a/=2;
    }
    return true;
}
 
long long int Power(long long int a, long long int b) {
    long long int result = a;
    for(long long int i = 1; i < b; i++) 
        result = result * a;
    return result;
}
 
int main(void) {
    int TestCase = 0;
    cin >> TestCase;
    while (TestCase --)
    {
        int n;
        cin >> n;
        if(CheckPow(n)) {
            cout << 0 << endl;
            continue;
        }
        string num = to_string(n);
        long long int now = 1;
        int result = 15;
        int weight = 9;
        //cout << (long long int)powl(10, 20) << endl;
        //cout << Power(10, 18) << endl;
        while (result > 1 && now < Power(10, 18)) {
            string nstr = to_string(now);
            int i = 0, j = 0;
            int trash = 0;
            for(i = 0; i < nstr.length(); i++) {
                for(j; j < num.length(); j++) {
                    if(nstr[i] == num[j]) 
                        break;
                    trash++;
                }
                if(j==num.length()) {
                    trash += nstr.length() - i;
                    break;
                }
                else j++;
            }
            result = min(result, trash + (int)(num.length()-j));
 
            now *= 2;
        }
        cout << result << endl;
    }
    
    return 0;
}

느낀점

처음 봤을 때 막막했지만, 오랜시간 고민해본 결과 해법을 알아내고 시간은 얼마 남지 않았었다.
결국 오류를 잡지 못하고 대회가 종료되고 말았다.

결국 int의 범위 때문에 큰 오류가 났었는데, 다음부턴 최대값을 정하고 작업을 하는게 안전할 것 같다.

https://codeforces.com/contest/1560/problem/C
Codeforces Round #739 (Div. 3)

C. Infinity Table

문제 요약

2차원배열 가장 왼쪽 위부터 시작하는 table이 있다. 이table은 다음과같은 패턴으로 순서대로 생성이 된다.

위와같은 패턴으로 table이 무한정 생성될 때 k가 존재하는 행과 열을 구하여라.

피드백

Input

1-st line : Testcase (1 <= t <= 100)
각 Testcase 마다
t-th line : 1개의 정수 (1 <= k <= 10⁹)

Output

각 Testcase 마다
2개의 정수 (r, c >= 1) space로 구분 : k가 위치하고있는 열과 행

문제 풀이

또 800점 문제이다. 또한 패턴만 구하면 간단하게 해결할 수 있었다.

0번째 열을 확인해보면 각각 n번째 행의 원소들이 n의 제곱인것을 확인할 수 있다.
다르게 말하면 0번째 행의 0보다 큰 n번째 열의 원소는 n-1의 제곱 + 1이라는 사실도 성립된다.
또한 변화하는 행과 열의 종류가 변경되는 시점은 n-1의 제곱 + (n-1)이기 때문에 k의 위치는 쉽게 구할 수 있었다.

최종 해설

먼저 정수형 sq를 선언하여 k의 제곱근(소수점부분은 제외)을 구하였다.

만약 소수점을 제외한 sq의 제곱이 k와 같다면, k의 위치는 0열 sq행으로 고정되기 때문에 예외를 두어 처리를 해 주었다.

다음으로 알아야 하는것은 k가 위치하고 있는 곳이 열이 변경되는 구간인지, 행이 변경되는 구간인지 알 필요가 있다.
먼저 행과 열이 바뀌는 구간은 sq의 제곱 + sq로 구할 수 있다. (행과 열이 만나는 시점)

따라서 해당 값보다 크게 되면, 가로로 배치되는 시점이므로 행의 위치는 sq+1로 고정이며 열의 위치는 sq+1의 제곱에서 k값을 뺀 값이 k가 위치하는 열의 번호가 된다.

또는

행과 열이 만나는 시점보다 k의 값이 작게 되면, 세로로 배치되는 시점이므로 열의 위치는 sq+1로 고정이며 행의 위치는 k에서 sq의 제곱을 뺀 값이 된다.

최종 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

#include <iostream>
#include <math.h>
 
using namespace std;
 
int main(void) {
    int TestCase = 0;
    cin >> TestCase;
    while (TestCase --)
    {
        int k;
        cin >> k;
        int sq = (int)sqrt(k);
        if(sq*sq == k) {
            cout << sq << " " << 1 << endl;
            continue;
        }
        if(k > sq*sq+sq) 
            cout << sq+1 << " " << sq-(k-(sq*sq)-sq)+2 << endl;
        else 
            cout << k-(sq*sq) << " " << sq+1 << endl;
    }
    
    return 0;
}

느낀점

어렵지 않았다. 간단한 공식을 알아내면 쉽게 풀 수 있는 문제였다.
앞에서 뻘짓한게 아까웠다..

https://codeforces.com/contest/1560/problem/B
Codeforces Round #739 (Div. 3)

B. Who’s Opposite?

문제 요약

원형의 식탁에서 회의를 하는데 인원은 모르고(짝수이다) 모든 사람은 서로 마주보는 상대가 있다.
각자의 번호는 1부터 시작해서 시계방향으로 숫자를 매긴다.

a 와 b가 마주보고 있을 때, c와 마주보고 있는 사람의 번호를 구하여라.

피드백

Input

1-st line : Testcase (1 <= t <= 10⁴)
각 Testcase 마다
t-th line : space로 구분된 3개의 정수 (1 <= a, b, c <= 10⁸)

Output

각 Testcase 마다
1개의 정수 d : c와 마주보고있는 숫자
답이 여러개일시 아무거나 출력, 답이 없으면 -1출력

문제 풀이

이문제 또한 어려운 문제는 아니였다. 규칙만 잘 찾으면 되는 문제였지만, 예상외로 해맸었다.

Attr 1 (Time Limit exceeded on test 2)

첫시도부터 굉장히 복잡하게 생각을 했는데 일단 무조건 규칙이 있을것이라고 예상을 하였다. 그래서 열심히 규칙을 찾아본 결과..
서로 마주보는 a와 b를 기준으로 a-n은 b-n을 마주보고 있다는 사실을 알게 되었다.
또한 계속 빼가다가 어느 한 수가 0에 도달하게 되면,
큰수 + (큰수 - n - 작은수)가 원탁에 앉아있는 총 인원 수가 나왔다. 복잡하다
또는 큰수-n과 작은수의 값이 같아지면, 큰수 + (작은수 - n) 의 값이 총 인원수가 되었다.

결국 for문으로 돌려서 위 두 케이스중 하나의 케이스가 나오게 되면 Loop를 빠져나가고 남은 값들을 계산하여 값을 도출해 냈다. 물론 결과는

시간 초과
최대 시간복잡도가 10⁴X10⁸ = 10¹²(약 1조…)가 나와버린다…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

#include <iostream>
#include <algorithm>
 
using namespace std;
 
int main(void) {
    int TestCase = 0;
    cin >> TestCase;
    while (TestCase --)
    {
        int a, b, c;
        cin >> a >> b >> c;
        int big = max(a, b);
        int small = min(a, b);
        int i, meet = small - 1;
        int result = -1;
        for (i = big-1; i > small && meet > 0; i--, meet--) {
            if (result == -1) {
                if(i == c) result = meet;
                else if(meet == c) result = i;
            }
        }
        //cout << "i = " << i << ", m = " << meet << endl;
        if(result == -1 && i > small && meet == 0) {
            if(c > small && c <= i) result = big + (c-small);
            else if(c > big && c <= (big + (i-small))) result = small + (c-big);
        }
        cout << result << endl;
    }
    
    return 0;
}

Attr 2 (Wrong answer on test 2)

시간초과로 한대 맞고난 뒤 for문으로 해결할 수 없는 문제라는 사실을 문제를 본지 40분만에 알아차렸다. 결국 다른 규칙을 찾다가 한가지 핵심적인 규칙을 깨닳을 수 있었다.

서로 마주보고있는 두 수의 간격은 무조건 전체 인원수의 절반이 된다.
이 규칙을 찾은 후 이 규칙을 가지고 코드를 짰다. 기본적으로 두 수의 간격을 구하고, 그 간격을 기준으로 c값이 작으면 전체 인원수의 절반을 더해주고, c값이 크면 전체 인원수의 절반을 빼주는 형식으로 정답을 구했다. 또한 몇가지의 예외사항을 넣어두었다.

앞에서 했던 for문 뻘짓을 왜했는지 이해가 되지 않았지만 8분만에 코드를 짜고 제출을 하였다.
그러나 결과는

오답
공식에는 문제가 없었다. 다른 예외사항이 있는듯했다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

#include <iostream>
#include <algorithm>

using namespace std;

int main(void) {
    int TestCase = 0;
    cin >> TestCase;
    while (TestCase --)
    {
        int a, b, c, result = -1;
        cin >> a >> b >> c;
        int big = max(a, b);
        int small = min(a, b);
        int dis = big - small;
        if(c > dis) result = c-dis;
        else if (c <= dis) result = c + dis;
        if(result > dis*2 || big > dis*2) result = -1;
        cout << result << endl;
    }
    
    return 0;
}

Attr 3 (Accepted!)

결국 또하나의 예외를 찾아내고 나서야 문제를 해결할 수 있었다.

“c가 전체 인원수보다 크면: a와 b가 마주보고 있는 원탁에는 c는 존재할 수 없다.”
결론적으로 이 예외조건을 추가하니 정상적으로 코드가 Accept 되었다.

최종 해설

서로 마주보고있는 두 수의 간격은 무조건 전체 인원수의 절반이 된다.

a와 b를 사용하여 전체 인원수의 절반을 구하고, 그 수를 기준으로 하여 c에 따라서 결과값을 구해주면 된다.
규칙만 잘찾으면 어렵지않게 풀 수 있는 문제였다. 괜히 반복문으로 접근해서 시간만 날렸다

?c가 전체 인원수의 절반보다 작거나 같으면:
정답 : c + 전체 인원수의 절반;

?아니면 c가 전체 인원수의 절반보다 크면:
정답 : c - 전체 인원수의 절반;

만약: 정답이 전체 인원수보다 크면:
정답 : -1;
제대로된 원탁이 아니다.

또는: c가 전체 인원수보다 크면:
정답 : -1;
a와 b가 마주보고 있는 원탁에는 c는 존재할 수 없다.

또는: a와 b중에 큰 수가 전체 인원수보다 크면:
정답 : -1;
a와 b중에 큰 수는 제대로된 원탁에 존재할 수 없다.

최종 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

#include <iostream>
#include <algorithm>
 
using namespace std;
 
int main(void) {
    int TestCase = 0;
    cin >> TestCase;
    while (TestCase --)
    {
        int a, b, c, result = -1;
        cin >> a >> b >> c;
        int big = max(a, b);
        int small = min(a, b);
        //총 인원수의 절반
        int dis = big - small;
        if(c > dis) result = c-dis;
        else if (c <= dis) result = c + dis;
        //답이 나오지 않는 경우 
        if(result > dis*2 || big > dis*2 || c > dis*2) result = -1;
        cout << result << endl;
    }
    
    return 0;
}

느낀점

원형탁자 -> 숫자 -> 순서대로 -> 반복문!! 일것이라고 안일하개 생각한게 문제가 되었다.
결국 초반에 반복문으로 계속 고민을 하다가 시간만 날려버리게 되었다.
문제를 해결하는 방법에 편견을 가지지 말고 다양한 방법을 생각해 봐야할 것 같다.

https://codeforces.com/contest/1560/problem/A
Codeforces Round #739 (Div. 3)

A. Dislike of Threes

문제 요약

Polycarp은 3을 싫어한다. 3으로 끝나는 문자와 3으로 나누어 떨어지는 문자를 제외하고 숫자를 세어서 n번째 숫자를 구해라

피드백

Input

1-st line : Testcase (1 <= t <= 100)
각 Testcase 마다
t-th line : 1개의 정수 (1 <= k <= 1000)

Output

각 Testcase 마다
1개의 정수 x : Polycarp이 싫어하지 않는 k-th 숫자

문제 풀이

정말 간단하게 풀 수 있다. 단순한 1차원 반복문을 사용하여 num이 3으로 나누어떨어지거나 3으로 끝나면(10으로 나누었을때 나머지가 3이면) 한번 더 더해서 카운트를 건너뛰어주었다.

최종 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

#include <iostream>
 
using namespace std;
 
int main(void) {
    int TestCase = 0;
    cin >> TestCase;
    while (TestCase --)
    {
        int k;
        cin >> k;
        int num = 0;
        for(int i = 1; i <= k; i++) {
            num++;
            while(num % 3 == 0 || num % 10 == 3) num++;
        }
        cout << num << endl;
    }
    
    return 0;
}

느낀점

800점대 문제면서 Div. 3 A번 문제라 정말 쉬웠다. 간단한 루프문으로 해결될줄은 몰랐지만 생각보다 빠르게 끝냈다.