딩코딩 : Computer Science 블로그

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

큰 수의 계산을 잘 구현해야 하는 문제이다.

2^100은

10^34 정도 되기 때문에

long long 은 최대 19자리이므로 long long 2개를 붙여쓰면 38자리까지 구현이 가능하다.

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


void _pow(int n){
    long long a = 0, b = 0, mod = 1'000'000'000'000'000'000;
    for(int i=0; i<n; i++){
        b*=2;
        a = 2 * a + 1;
        b += a / mod;
        a %= mod;
    }
    if(b>0) cout << b << a << '\n';
    else cout << a << '\n';
}


//start : 0 , mid:1, end:2
void moveBlock(int start, int end){
    cout << start+1 << ' ' << end+1 << '\n';
}


void hanoi(int n, int start, int mid, int end){
    if(n==0) return;
    hanoi(n-1, start, end, mid);
    //마지막꺼 옮기기
    moveBlock(start, end);
    hanoi(n-1, mid, start, end);
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);

    int n;
    cin >> n;
    _pow(n);

    if(n<=20) {
        hanoi(n, 0, 1, 2);
    }

    return 0;
}

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

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

int stx,sty, enx,eny;

bool inAndOut(int x, int y, int r){
    int startToCircleDist = (stx-x)*(stx-x) + (sty-y)*(sty-y);
    int endToCircleDist = (enx-x)*(enx-x) + (eny-y)*(eny-y);
    int R = r*r;

    if((startToCircleDist > R && endToCircleDist < R)||(startToCircleDist < R && endToCircleDist > R)) return true;
    return false;
}


int main() {
    ios::sync_with_stdio(0); cin.tie(0);

    int T;
    cin>> T;
    for(int t=0;t<T; t++){
        int n;
        cin >> stx >> sty >> enx >> eny >> n;

        int ans = 0;
        for(int i=0; i<n; i++){
            int x, y, r;
            cin >> x >> y >> r;
            if(inAndOut(x,y,r)) ans++;
        }
        cout << ans << '\n';
    }

    return 0;
}

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

import java.util.Scanner;

class Tree {
    class Node{
        int data;
        Node left, right;
        Node(int data){
            this.data = data;
        }
    }
    Node root;
    static int pIndex = 0;

    public void buildTreeByInPost(int in[], int post[]){
        pIndex = post.length - 1;
        root = buildTreeByInPost(in ,post, 0, in.length-1);
    }

    private Node buildTreeByInPost(int in[], int post[], int start, int end){
        if(start > end) return null;
        Node node = new Node(post[pIndex--]);
        if(start==end) return node;
        int mid = search(in, start, end, node.data);

        node.right = buildTreeByInPost(in, post, mid+1, end);
        node.left = buildTreeByInPost(in, post, start, mid-1);
        return node;
    }

    private int search(int arr[], int start, int end, int value){
        int i;
        for(i=start; i<=end; i++){
            if(arr[i]==value) return i;
        }
        return i;
    }

    void printPreorder(Node node){
        if(node == null) return;
        System.out.print(node.data + " ");
        printPreorder(node.left);
        printPreorder(node.right);
    }
}

public class Main {
    public static void main(String args[]){
        int n;
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        int[] in = new int[n];
        int[] post = new int[n];

        for(int i=0; i<n;i++){
            in[i] = sc.nextInt();
        }

        for(int i=0; i<n;i++){
            post[i] = sc.nextInt();
        }

        Tree tree = new Tree();
        tree.buildTreeByInPost(in, post);
        tree.printPreorder(tree.root);
    }
}

InOrder + preOrder 결과나

InOrder + postOrder 결과가 있어야 원본 트리를 복원할 수 있다.

class Tree {
    class Node{
        int data;
        Node left, right;
        Node(int data){
            this.data = data;
        }
    }
    Node root;
    static int pIndex = 0;

    public void buildTreeByInPre(int in[], int pre[]){
        pIndex = 0;
        root = buildTreeByInPre(in, pre, 0, in.length-1);
    }
    private Node buildTreeByInPre(int in[], int pre[], int start, int end){
        if(start > end) return null;
        Node node = new Node(pre[pIndex++]);
        if(start == end) return node;
        int mid = search(in, start, end, node.data);
        node.left = buildTreeByInPre(in, pre, start, mid-1);
        node.right = buildTreeByInPre(in, pre, mid+1, end);
        return node;
    }

    public void buildTreeByInPost(int in[], int post[]){
        pIndex = post.length - 1;
        root = buildTreeByInPost(in ,post, 0, in.length-1);
    }

    private Node buildTreeByInPost(int in[], int post[], int start, int end){
        if(start > end) return null;
        Node node = new Node(post[pIndex--]);
        if(start==end)return node;
        int mid = search(in, start, end, node.data);

        node.right = buildTreeByInPost(in, post, mid+1, end);
        node.left = buildTreeByInPost(in, post, start, mid-1);
        return node;
    }

    private int search(int arr[], int start, int end, int value){
        int i;
        for(i=start; i<=end; i++){
            if(arr[i]==value) return i;
        }
        return i;
    }
    void printInorder(Node node){
        if(node == null) return;
        printInorder(node.left);
        System.out.print(node.data + " ");
        printInorder(node.right);
    }
}

public class Main {
    public static void main(String args[]){
        Tree tree = new Tree();
        int[] pre = {4,2,1,3,6,5,7};
        int[] in = {1,2,3,4,5,6,7};
        int[] post = {1,3,2,5,7,6,4};
        tree.buildTreeByInPre(in, pre);
        tree.printInorder(tree.root);
        System.out.println();
        tree.buildTreeByInPost(in, post);
        tree.printInorder(tree.root);
    }
}

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

#include <bits/stdc++.h>

using namespace std;

int N, dp[1003];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    dp[1] = 1;
    dp[2] = 0;
    dp[3] = 1;
    dp[4] = 1;

    cin >> N;

    for(int i=5; i<=1000; i++){
        dp[i] = max({!dp[i-4], !dp[i-3], !dp[i-1]});
    }

    if(dp[N]) cout << "SK";
    else cout << "CY";

    return 0;
}

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

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int num = 1;
    while (1) {
        int N;
        cin >> N;
        if (N == 0) break;

        int a, b, c;
        cin >> a >> b >> c;

        c = b + c;

        int dp[3], pre[3];
        cin >> dp[0] >> dp[1] >> dp[2];
        dp[0] += b;
        dp[1] = min({dp[0], b, c}) + dp[1];
        dp[2] = min({b, c, dp[1]}) + dp[2];

        for (int i = 1; i <= N - 2; i++) {
            int x, y, z;
            pre[0] = dp[0];
            pre[1] = dp[1];
            pre[2] = dp[2];

            cin >> x >> y >> z;

            dp[0] = x + min(pre[0], pre[1]);
            dp[1] = y + min({pre[0], pre[1], pre[2], dp[0]});
            dp[2] = z + min({pre[1], pre[2], dp[1]});

        }
        cout << num++ << ". " << dp[1] << '\n';
    }

    return 0;
}

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

#include <bits/stdc++.h>

using namespace std;
int N, day[1'500'003], preMax;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N;
    for (int i = 1; i <= N; i++) {
        int a, b;
        cin >> a >> b;

        day[i] = max(day[i], preMax);
        if (i + a <= N + 1) {
            day[i + a] = max(day[i + a], day[i] + b);
        }
        preMax = max(preMax, day[i]);
    }

    int ans = 0;
    for (int i = 1; i <= N + 1; i++) {
        ans = max(ans, day[i]);
    }

    cout << ans;
    return 0;
}

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

#include <bits/stdc++.h>

using namespace std;

int N, K, arr[101][101];

void addFish() {
    int min = INT_MAX;
    for (int i = 1; i <= N; i++) {
        if (arr[1][i] < min) min = arr[1][i];
    }

    for (int i = 1; i <= N; i++) {
        if (arr[1][i] == min) arr[1][i]++;
    }
}

void jumpBlock() {
    arr[2][2] = arr[1][1];
    arr[1][1] = 0;

    int stx = 2, sty = 2;
    int row = 2, col = 1;
    int cnt = 1;

    while (stx + sty <= N) {
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                arr[2 + j][sty + (row - i)] = arr[stx - i][sty - j];
                arr[stx - i][sty - j] = 0;
            }
        }

        sty += stx;
        if (cnt % 2 == 1) {
            col++;
        } else {
            row++;
            stx++;
        }

        cnt++;
    }
}


void fishControl() {
    int dx[4] = {1, 0, -1, 0};
    int dy[4] = {0, 1, 0, -1};

    int tmp[101][101];
    memset(tmp, 0, sizeof(tmp));

    for (int i = 1; i <= 100; i++) {
        for (int j = 1; j <= N; j++) {
            if (arr[i][j]) {
                int sum = 0;
                int minus = 0;

                for (int k = 0; k < 4; k++) {
                    int nx = i + dx[k];
                    int ny = j + dy[k];
                    if (nx <= 0 || nx > 100 || ny <= 0 || ny > N) continue;
                    if (arr[nx][ny] == 0)continue;

                    int diff = (arr[i][j] - arr[nx][ny]) / 5;

                    if (diff == 0) continue;
                    else if (diff > 0) {
                        minus += diff;
                    } else {
                        sum += abs(diff);
                    }
                }
                tmp[i][j] = arr[i][j] - minus + sum;
            }
        }
    }
    swap(tmp, arr);
}

void putDown() {
    int idx = 1;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= 100; j++) {
            if (arr[j][i]) {
                arr[1][idx++] = arr[j][i];

                if (j == 1 && i == idx - 1) continue;
                arr[j][i] = 0;
            }
        }
    }
}


void reJumpBlock() {
    for (int i = 1; i <= N / 2; i++) {
        arr[2][N - i + 1] = arr[1][i];
        arr[1][i] = 0;
    }

    for (int i = 0; i < N / 4; i++) {
        for (int j = 0; j < 2; j++) {
            arr[3 + j][N - i] = arr[2 - j][N / 2 + 1 + i];
            arr[2 - j][N / 2 + 1 + i] = 0;
        }
    }
}

bool isEnd() {
    int max = -1;
    int min = INT_MAX;

    for (int i = 1; i <= N; i++) {
        if (max < arr[1][i]) max = arr[1][i];
        if (min > arr[1][i]) min = arr[1][i];
    }
    return (max - min <= K);
}


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> K;
    for (int i = 1; i <= N; i++) {
        cin >> arr[1][i];
    }

    if (isEnd()) {
        cout << 0 << '\n';
        return 0;
    }

    int ans = 1;
    while (1) {
        addFish();
        jumpBlock();
        fishControl();
        putDown();
        reJumpBlock();
        fishControl();
        putDown();
        if (isEnd()) break;
        ans++;
    }


    cout << ans << '\n';

    return 0;
}