아인스트라세의 SW 블로그

백준저지 1300번 문제 "K번째 수" 문제 풀이입니다.

https://www.acmicpc.net/problem/1300

바이너리 서치로 풀이하였습니다.

N이 주어졌을 때, 특정 수 x보다 작거나 같은 수의 개수를 O(N)만에 계산할 수 있는데, 이를 이용하여

x보다 작거나 같은 수의 개수가 K와 비슷해질때까지 바이너리 서치를 합니다.

x보다 작거나 같은 수의 개수를 num(x) 라 할 때

바이너리 서치와 약간 다른 점은, K와 완전히 같은 num(x)가 존재하지 않을 수 있습니다.

따라서 K보다 큰 num(x) 중 최소 값을 갖는 x를 구해야 하며, num(x) == num(x+1) == ... == num(x+a) 와 같이 같은 값들을 가지는 num(x)들이 있을 수 있습니다. 이들 중에서는 가장 작은 x값이 정답이 됩니다.

num(x) == num(x+1) == ... == num(x+a)와 같은 관계에서는 x는 실제 N*N 매트릭스에 존재하는 값이지만, x+1은 존재하지 않는 값이기 때문입니다.

코드는 아래와 같습니다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll num(ll v, ll N) {
    ll ret = 0;
    //v보다 작거나 같은 원소 개수를 리턴함
    for (int i = 1; i <= N; i++) {
        ret += min(N, v / i);
    }
    return ret;
}
ll solve(ll N, ll K) {
    //binary search 할 예정인데
    // K보다 크거나 같은 값 중 최소 값 구할 예정. (중복 수 있을 수 있으므로)
    // K와 같은 값이면 그중에 가장 작은 값
    ll l = 1, r = N*N;
    while (l < r) {
        ll m = (l + r) / 2;
        long long n = num(m, N);
        if (n == K) {
            ll v = m - 1;
            while (n == num(v, N)) {
                v--;
            }
            r = v + 1;
            break;
        }
        else if (n > K) {
            r = m;
        }
        else if (n < K) {
            l = m + 1;
        }
    }
    return r;
}

int main() {
    ll N, K; cin >> N >> K;
    cout << solve(N, K) << endl;

    return 0;
}

구글 코드잼 2019년도 예선전 후기다. 간단하게 작성해보고자 한다.

방금 글 쓰다가 한번 날아가서 조금 대충쓰고 싶어졌다.

퀄리피케이션 라운드는 절대평가(30점)에다가 27시간동안이나 대회를 하므로 간단하게 풀어버리고

약속에 가려고 했으나, 현실은 약속시간 내내 3번째 문제 솔루션을 생각했다.

가볍게 첫번째 문제 Foregone Solution 문제를 보았다. 히든케이스 10^100를 커버하기 위해 익숙하지 않은

파이썬으로 해결했다.

모든 4를 3으로 바꾸어 버리는 식으로 코드를 짰다.

tc=int(input())

def solve(n):
    a=int(str(n).replace('4', '3'))
    b=n-a
    return str(a) + " " + str(b)
for t in range(1, tc+1):
    n=int(input())
    ans=solve(n)
    print ("Case #" + str(t) + ": " + ans)

두번째 문제 You can go your own way

대충 문제 읽어보니까 솔루션이 떠올랐는데, 너무 간단해서 함정이 있나 조금 생각했다. E와 S를 서로 바꾸어주면 간단히 해결된다.

요녀석은 빅인티저같은게 필요가 없어서 주력언어인 C++로 작성했다.

#include <bits/stdc++.h>
using namespace std;

int main() {
    int tc;
    scanf("%d", &tc);
    for (int t=1; t<=tc; t++) {
        int n; scanf("%d", &n);
        string s;
        cin >> s;
        printf("Case #%d: ", t);
        for (size_t i=0; i < s.length(); i++) {
            if (s[i] == 'S') putchar('E');
            else putchar('S');
        }
        putchar('\n');
    }
	return 0;
}

세번째 문제, 욕심부리다가 엄청 오랫동안 생각했다.

간단하게 gcd를 구해서 하면 될 거라 생각했는데, 같은 숫자가 나오는 것을 간과했어서  WA를 엄청나게 뿜었다.

파이썬으로 제출한 것은 RE도 자주나왔다. 이유는 아직도 모르겠다..

원문이 AAA ABA 형식으로 나오게 되면, 인접한 cipher int value 가 동일한 값이 나오기 때문에 그냥 gcd를 구하면 1이 나오게 된다.

이 점을 유의해야 한다는 것을 까먹었다.

Runtime Error 때문에 C++로 솔루션을 작성해 보고, 후에 Python 으로 바꾸어서 히든케이스를 대비했다.

사용된 소수들은 인접 값이 다를때만 gcd로 죄다 구하면 되고, 해독할때는 소수 하나만 찾아내서 양옆으로 propagation 시키면 됬던 풀이이다.

일단 씨쁠쁠 풀이이다.

#include <bits/stdc++.h>
using namespace std;

int N, L;  
int plainValue[105];

int main() {
    int tc; cin >> tc;
    for (int t=1; t<=tc; t++) {
        memset(plainValue, 0, sizeof(plainValue));
        cin >> N >> L;
        vector<int> ciphers;
        set<int> primes;
        map<int, char> int2char;
        map<char, int> char2int;
        ciphers.clear();
        primes.clear();
        int2char.clear();
        char2int.clear();
        for (int i=0; i < L; i++) {
            int tmp; cin >> tmp;
            ciphers.push_back(tmp);
        }
        for (int i=0; i< L-1; i++) {
            if (ciphers[i] != ciphers[i+1]) {
                int cd = __gcd(ciphers[i], ciphers[i+1]);
                primes.insert(cd);
                primes.insert(ciphers[i]/cd);
                primes.insert(ciphers[i+1]/cd);
            }
        }
        char c = 'A';
        for (auto& p : primes) {
            if (int2char.find(p) == int2char.end()) {
                char2int[c] = p;
                int2char[p] = c++;
            }
        }
        
        int idx, pval, ppval;
        for (idx=0; idx < L-1; idx++) {
            if (ciphers[idx] != ciphers[idx+1]) {
                int cd = __gcd(ciphers[idx], ciphers[idx+1]);
                plainValue[idx+1] = cd;
                pval = ciphers[idx+1] / cd;
                ppval = ciphers[idx] / cd;
                break;
            }
        }
        
        
        for (int i=idx; i >= 1; i--) {
            plainValue[i] = ppval;
            ppval = ciphers[i-1] / ppval;
        }
        plainValue[0] = ppval;
        
        for (int i=idx+2; i < L; i++) {
            plainValue[i] = pval;
            pval = ciphers[i] / pval;
        }
        plainValue[L] = pval;
        
        printf("Case #%d: ", t);
        for (int i=0; i <= L; i++) {
            putchar(int2char[plainValue[i]]);
        }
        putchar('\n');
    }
}

이렇게 짠 녀석을 그대로 파이썬으로 옮기면 히든케이스도 커버할 수 있다.

def gcd(x,y):
    while(y):
        x,y=y,x%y
    return x
    
def make_unique(l):
    t = []
    for v in l:
        if len(t)==0 or t[-1] != v:
            t.append(v)
    return t
   
tc=int(input())
for t in range(1, tc+1):
    plainValue = [0 for i in range(0, 110)]
    N, L = map(int, input().split(' '))
    ciphers = list(map(int, input().split(' ')))
    primes = []
    int2char = {}
    
    for i in range(0, L-1):
        if ciphers[i] != ciphers[i+1]:
            cd = gcd(ciphers[i], ciphers[i+1])
            primes.append(cd)
            primes.append(ciphers[i]//cd)
            primes.append(ciphers[i+1]//cd)
            
    primes.sort()
    primes = make_unique(primes)
    c = 'A'
    for p in primes:
        if int2char.get(p) == None:
            int2char[p] = c
            c = chr(ord(c) + 1)
            
    idx = 0
    pval = 0
    ppval = 0
    
    for idx in range(0, L-1):
        if ciphers[idx] != ciphers[idx+1]:
            cd = gcd(ciphers[idx], ciphers[idx+1])
            plainValue[idx+1] = cd
            pval = ciphers[idx+1] // cd
            ppval = ciphers[idx] // cd
            break
    
    for i in range(idx, 0, -1):
        plainValue[i] = ppval
        ppval = ciphers[i-1] // ppval
    plainValue[0] = ppval
    
    for i in range(idx+2, L):
        plainValue[i] = pval
        pval = ciphers[i]  // pval
    plainValue[L] = pval
    
    
    ans = ""
    for i in range(0, L+1):
        ans += int2char[plainValue[i]]
    print ("Case #" + str(t) + ": " + ans)

마지막 문제의 경우는 아직 풀지를 못했는데, 나중에 여유가 되면 한번 풀어보고 올려보도록 하겠다.

백준 17135번 문제 캐슬 디펜스 문제 풀이입니다.

https://www.acmicpc.net/problem/17135

N, M, D값이 크지 않으므로, 하나하나 다 따라가는 시뮬레이션 방식으로 풀이하면 됩니다.

test(a,b,c) 함수는 궁수의 위치가 각각 (N, a) (N, b) (N, c)일때 최대로 잡을 수 있는 적의 수를 리턴합니다.

choose_turn 함수는 각각의 턴마다 각각의 궁수가 공격할 적의 위치를 set에 추가합니다.

#include <bits/stdc++.h>
using namespace std;

int N, M, D;
int field[16][16];
typedef struct _Pos {
    int x, y;
    bool operator<(const struct _Pos& rhs) const {
        return x != rhs.x ? x < rhs.x : y < rhs.y;
    }
} Pos;
inline int dist(int x1, int y1, int x2, int y2) {
    return abs(x1-x2) + abs(y1-y2);
}
inline int dist(Pos p1, Pos p2) {
    return abs(p1.x - p2.x) + abs(p1.y - p2.y);
}
void choose_target(int mmap[][16], set<Pos>& kset, int turn, int archer_pos) {
    Pos archer = { N, archer_pos };
    Pos vic_pos = { 1000, 1000 };
    int pd = dist(archer, vic_pos); //previous dist
    for (int i=0; i< N - turn; i++) {
        for (int j=0; j < M; j++) {
            if (mmap[i][j] == 0) continue;
            Pos epos = { i + turn, j };
            int d = dist(archer, epos);
            if (d <= D) {
                if (d < pd || (d == pd && epos.y < vic_pos.y)) {
                    pd = d;
                    vic_pos = epos;
                }
            }
        }
    }
    if (vic_pos.x != 1000) kset.insert({ vic_pos.x - turn, vic_pos.y });
}
int test(int a, int b, int c) {
    //archer pos = (N, a) (N, b) (N, c)
    int kill = 0; //ret val
    int mmap[16][16];
    for (int i=0; i < N; i++)
        for (int j=0; j < M; j++)
            mmap[i][j] = field[i][j];
    
    set<Pos> kill_set;
    kill_set.clear();
    for (int t=0; t < N; t++) {
        //for each turn
        choose_target(mmap, kill_set, t, a);
        choose_target(mmap, kill_set, t, b);
        choose_target(mmap, kill_set, t, c);
        kill += (int)kill_set.size();
        for (auto& v : kill_set) {
            mmap[v.x][v.y] = 0;
        }
        kill_set.clear();
    }
    return kill;
}
int main() {
    cin >> N >> M >> D;
    for (int i=0; i < N; i++)
        for (int j=0; j < M; j++)
            cin >> field[i][j];
    
    int ans = 0;
    for (int i=0; i < M-2; i++) 
        for (int j=i+1; j < M-1; j++)
            for (int k=j+1; k < M; k++)
                ans = max(ans, test(i,j,k));
            
    cout << ans << endl;
	return 0;
}