ABC 336 - 3sol

A - Long Loong

n이 주어졌을 때, L, o, n, g로 이루어진 문자열을 출력하는 문제

문자열의 길이는 n + 3이고, 문자열 중 o의 개수가 n개여야한다.

 

간단하게 L을 출력하고, n개의 o를 출력하고, ng를 출력시키면 된다.

#include <iostream>
using namespace std;
int main(){
    int n; cin >> n;
    cout << "L";
    while(n--) cout << "o";
    cout << "ng";
}

---

 

B - CTZ 

주어진 수를 이진수로 나타냈을 때, 처음으로 1이 등장하기까지 몇 개의 0이 존재하는지 묻는 문제

 

이를 위한 ctz 함수가 존재한다고 하는데,

사실 이진수를 만들면 되므로 간단하게 해결할 수 있었다.

#include <iostream>
using namespace std;
int main(){
    int n, cnt=0; cin >> n;
    while(n!=0){
        if(n%2==0) cnt++;
        else break;
        n/=2;
    }
    cout << cnt;
}

---

 

C - Even Digits

0, 2, 4, 6, 8로만 이루어진 0이 아닌 정수를 나열했을 때 N번째 큰 수는 무엇인지 묻는 문제

 

일단 N의 범위가 10^12이므로 하나하나 계산하기에는 무리가 있다.

그래서 규칙을 찾아 분할정복으로 접근했다.

먼저 N자리 자연수의 개수를 세보면,

자릿수가 1 인 경우

0, 2, 4, 6, 8이다.

직관적으로 5개임을 알 수 있다.

 

자릿수가 2인 경우

20, 22, 24, 26, 28, ... 80, 82, 84, 86, 88 이다.

즉, 십의 자리 수가 2인 경우 5개, 4인 경우 5개 ... 8인 경우 5개이므로 현재까지 총 20개이다.

현재까지 누적은 25개이다.

 

자릿수가 3인 경우

200, 202, 204, 206, 208, 220, 222 ... 880, 802, 804, 806, 808, ... 880, 882, 884, 886이므로

백의 자리가 2인 경우에서

다시 십의자리가 2인 경우로 들어가고, 이는 앞서 구했던 자릿수가 2인 경우이다.

여기서 십의 자리는 2, 4, 6, 8 4개가 존재하고, 각각에 자릿수가 2인 경우가 딸려오므로

4 * 25해서 총 100개가 존재한다.

그러므로 현재까지 누적은 125개이다.

 

즉, 5^자릿수 만큼 개수가 늘어나는 것을 쉽게 알 수 있으므로

5씩 나누어가며 자릿수 및 해당하는 숫자를 구할 수 있다.

#include <iostream>
#include <string>
using namespace std;
string s;
void check(long long n, long long cnt){
    if(!cnt) return;
    if(n>cnt*4){
        s+="8";
        check(n-cnt*4, cnt/5);
    }
    else if(n>cnt*3){
        s+="6";
        check(n-cnt*3, cnt/5);
    }
    else if(n>cnt*2){
        s+="4";
        check(n-cnt*2, cnt/5);
    }
    else if(n>cnt){
        s+="2";
        check(n-cnt, cnt/5);
    }
    else{
        s+="0";
        check(n, cnt/5);
    }
}
int main(){
    long long n, cnt=1; cin >> n;
    while(1){
        cnt*=5;
        if(cnt>n){
            cnt/=5;
            break;
        }
    }
    check(n, cnt);
    cout << stoll(s);
}

---

 

D - Pyramid

n개의 자연수로 이루어진 배열에서 피라미드 형태의 그림을 만들 때 피라미드의 최대 크기를 구하는 문제

 

가령 

5

2 2 3 1 1 로 주어진 경우

만들 수 있는 피라미드는 1, 2, 3번 원소를 이용한 1 2 1이 될 것이다.

이를 앞에서부터 비교해가며 해당 높이의 좌 / 우를 비교하기는 어려우므로,

좌 / 우 배열을 각각 만들어 최종적인 높이를 구해주면 된다.

 

배열의 높이는 현재 높이가 아무리 높더라도 좌측의 높이보다 1큰 수가 저장될 것이다. 

그러므로 l 배열을 만들어 왼쪽부터 계산하여 최대 높이는 l[i - 1] + 1과 현재 입력받은 높이의 최솟값으로 이루어진다.

마찬가지로 r 배열을 오른쪽부터 계산하는 배열을 만들어주면 된다.

#include <iostream>
using namespace std;
int l[200002], r[200002], dp[200002];
int main(){
    int n, ans=-1; cin >> n;
    for(int i=1; i<=n; i++) cin >> dp[i];
    for(int i=1; i<=n; i++) l[i]=min(l[i-1]+1, dp[i]);
    for(int i=n; i>=0; i--) r[i]=min(r[i+1]+1, dp[i]);
    for(int i=1; i<=n; i++) ans=max(ans, min(l[i], r[i]));
    cout << ans;
}