구글 킥스타트(Kickstart) 2021 Round B 문제풀이

알고리즘/킥스타트 2021. 6. 29. 00:32

킥스타트 : https://codingcompetitions.withgoogle.com/kickstart

Kick Start - Google’s Coding Competitions

Hone your coding skills with algorithmic puzzles meant for students and those new to coding competitions. Participate in one round or join them all.

codingcompetitions.withgoogle.com

한동안 구글 킥스타트를 까먹고 있다가 오랜만에 풀어봤다. 확실히 구글배 알고리즘문제들은 알고리즘 지식을 묻기보다는 알고리즘적 사고력을 묻는듯한 문제들로 이루어져있다. 그래서 확실히 더 어렵게 느껴지긴 하다.

문제 1. Increasing Substring

문제 1번은 역시 쉽게 나온다. 그냥 단순하게 array 한번씩 쭈욱 탐색하면서 증가하는 알파벳이면 길이를 증가, 아니면 1로 초기화 이 과정을 거치면 된다.

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <queue>
#include <memory>
#include<cstring>
#include <string>

using namespace std;

typedef long long ll;

int testn;
ll n;
char str[200000];
int dp[200000];

int main()
{
    // cin.tie(NULL);
    // ios::sync_with_stdio(false);
    cin >> testn;

    for(int tn=1; tn<=testn; tn++){
        cin >> n;
        for(int i=0; i<n; i++)
            cin >> str[i];

        dp[0] = 1;
        for(int i=1; i<n; i++){
            if(str[i-1] < str[i]){
                dp[i] = dp[i-1] + 1;
            }
            else{
                dp[i] = 1;
            }
        }
        cout << "Case #"<<tn << ": ";
        for(int i=0; i<n; i++)
            cout << dp[i]<< " ";
        cout << '\n';
    }
 


    return 0;
}

문제 2번. Longest Progression

2번부터 문제가 확 어려워졌다. 배열 내에서 최대 1개의 원소를 다른 값으로 바꾸어 가장 긴 등차 수열을 구하는 문제이다. 어찌 풀까 고민하다가 다음과 같은 특징을 발견했다. 일단 길이 K인 등차수열이 존재하면 K < N 이기만 하면 무조건 K+1 인 등차수열을 만들수 있다. (양 끝 원소값 하나만 바꾸면 되므로) 그런데 만약 길이 K인 등차수열의 등차가 a라고 하고 K+1 위치의 원소 값을 바꾼다 했을때 array[K] +2a = array[K+2] 를 만족하게되면 등차수열은 K+1이 아닌 그 이상이 될 것이다. 그래서 i 위치에서 시작하는 가장 긴 등차수열길이 값을 저장하는 start[i] 와 i 위치에서 끝나는 가장 긴 등차수열길이 값을 저장하는 end[i] 배열을 초기화 해준다음에 만약 array[i-1] + 2a == array[i+1] 를 만족하면 end[i-1] + 1 + start[i+1] 의 값은 최대값의 후보가 될수 있다. 그래서 i 를 1~N 인경우만 탐색하면 되므로 O(N) 복잡도 내에서 문제를 해결할 수 있다.

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <queue>
#include <memory>
#include<cstring>
#include <string>

using namespace std;

typedef long long ll;

int testn;
ll n;

int s[300001];
int start[300001], en[300001];
int start_c[300001], end_c[300001];
int cha;

int main()
{
    cin.tie(NULL);
    ios::sync_with_stdio(false);
    cin >> testn;

    for(int tn=1; tn<=testn; tn++){
        cin >> n;
        for(int i=1; i<=n; i++)
            cin >> s[i];
        
        start[n] = 1;
        start[n-1] = 2;
        cha = s[n] - s[n-1];
        start_c[n] = 0;
        start_c[n-1] = cha;

        for(int i=n-2; i>=1; i--){
            int c = s[i+1]-s[i];
            if(c==cha){
                start[i] = start[i+1] + 1;
                start_c[i] = c;
            }
            else{
                start[i] = 2;
                start_c[i] = c;
            }
            cha = c;
        }

        en[1] = 1;
        en[2] = 2;
        cha = s[2]-s[1];
        end_c[1] = 0;
        end_c[2] = cha;

        for(int i=3; i<=n; i++){
            int c = s[i]-s[i-1];
            if(c==cha){
                en[i] = en[i-1] + 1;
                end_c[i]=c;
            }
            else{
                en[i] = 2;
                end_c[i] = c;
            }
            cha = c;
        }
  
        int m = max(start[1], start[2]+1);
        m = max(en[n], m);
        m = max(en[n-1]+1, m);

        for(int i=3; i<n-1; i++){
            m = max(m, en[i-1]+1);
            m = max(m, start[i+1]+1);

            if(s[i-1]+2*end_c[i-1] == s[i+1]){
                m = max(m, en[i-1]+2);
              
                if(end_c[i-1] == start_c[i+1]){
                    m = max(m, en[i-1]+start[i+1]+1);   
                }
            }
            if(s[i+1]-2*start_c[i+1] == s[i-1]){
               
                m = max(m, start[i+1]+2);
                if(end_c[i-1] == start_c[i+1]){
                    m = max(m, en[i-1]+start[i+1]+1);   
                }
            }
        }

        if(n==3){
            m = max(m, 3);
        }
        if(n>3){
            if(s[3] - 2*start_c[3] == s[1]){
                m = max(m, start[3]+2);
            }

            if(s[n-2] + 2*end_c[n-2] == s[n]){
                m = max(m, en[n-2]+2);
            }
        }

        

        cout << "Case #"<<tn << ": " <<m<<'\n';
        
    }
 


    return 0;
}

문제 3. Consecutive Primes

2개의 연속하는 최대한 큰 소수를 구해야 하는데 이 2개의 소수의 곱이 Z이 넘기면 안되는 문제이다.

이 문제의 힌트는 우리가 prime()함수를 구현할때를 생각하면 얻을 수 있다. 아래 처럼 우리는 x가 소수인지 판별하기 위해 1부터 x까지 모두 나누어 보는것이 아닌 root(x) 까지만 구한다. 그 이상은 의미가 없기 때문이다.

bool isprime(ll x){
    ll root = sqrt(x);
    if(x==2 || x==3) return true;

    for(ll i=2; i<=root; i++){
        if(x%i == 0) return false;
    }
    return true;
}

이처럼 생각해보면 우리가 구하고자하는 소수는 root(Z) 주변에 있을 것이라고 추측이 가능해진다. 그래서 root(Z)에서 1씩 빼면서 소수판별을해 소수 2개를 구하고, 마찬가지로 root(Z)에서 1씩 더하며 소수 1개를 구하면, 이 3개의 소수중에서 2개가 우리가 구하고자하는 답인것을 알 수 있다.

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <queue>
#include <memory>
#include<cstring>
#include <string>
#include <math.h>

using namespace std;

typedef long long ll;

int testn;
ll n;

bool isprime(ll x){
    ll root = sqrt(x);
    if(x==2 || x==3) return true;

    for(ll i=2; i<=root; i++){
        if(x%i == 0) return false;
    }
    return true;
}


int main()
{
    cin.tie(NULL);
    ios::sync_with_stdio(false);
    cin >> testn;

    for(int tn=1; tn<=testn; tn++){
        cin >> n;

        ll ans;


        ll start = (long long)sqrt(n);
        ll low[2];
        int num=0;
        while(true){
            if(isprime(start)){
                low[num++] = start;
            }
            start--;
            if(num==2) break;
        }
        start = (long long)(sqrt(n)+1);
        ll big;
        
        while(true){
            if(isprime(start)){
                big = start;
                break;
            }
            start++;
        }

        if(big*low[0] <= n) ans = big*low[0];
        else{
            ans = low[1]*low[0];
        } 

        cout << "Case #"<<tn << ": " <<ans<<'\n';
        
    }

    return 0;
}

문제 4. Truck Delivery

'알고리즘 > 킥스타트' 카테고리의 다른 글

구글 킥스타트(Kickstart) 2021 Round A 문제풀이 (0)	2021.03.24

ABOUT ME

DOOWN DOOWN

문제 1. Increasing Substring

문제 2번. Longest Progression

문제 3. Consecutive Primes

'알고리즘 > 킥스타트' 카테고리의 다른 글

티스토리툴바

ABOUT ME

문제 1. Increasing Substring

문제 2번. Longest Progression

문제 3. Consecutive Primes

'알고리즘 > 킥스타트' 카테고리의 다른 글

관련글 관련글 더보기

티스토리툴바