Atcoder Boot camp Problems Medium 1 ~ 5

 

1. B - Trained?

 

코드

import java.io.*;
import java.util.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
 
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n + 1];
        boolean[] visited = new boolean[n + 1];
        for (int i = 1; i <= n; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
 
        int cur = 1;
        visited[cur] = true;
        int ans = 0;
        while (cur != 2) {
            if (!visited[arr[cur]]) {
                cur = arr[cur];
              	visited[cur] = true;
                ans++;
            } else break;
        }
 
        bw.write((cur == 2 ? ans : -1) + "");
 
        bw.flush();
        bw.close();
        br.close();
    }
}

 

 

2. A - Irreversible operation

 

코드

import java.io.*;
import java.util.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
 
        String str = br.readLine();
        long cnt = 0;
        long ans = 0;
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) == 'W') {
                ans += cnt;
            } else if (str.charAt(i) == 'B') {
                cnt++;
            }
        }
 
        bw.write(ans + "");
 
        bw.flush();
        bw.close();
        br.close();
    }
}

 

 

3. A - ><

 

개선

 - 결과값을 저장하는 배열에 포커싱을 두고 입력 받은 문자열을 처리한다는 접근보다 입력 받은 문자열을 기준으로 결과값을 만들어낸다는 접근이 생각이 더 편했던 문제.

 - 현재 값이 이전 값에 따라 결정되어 따로 count 변수를 이용할 필요없이 이전 값을 이용해 현재 값을 채울 수 있다. 코드의 의미가 좀 더 명확해지고 깔끔해진다. 첫 제출 코드는 꽤 지저분했다.

 - stream을 이용하면 코드를 줄일 수 있다. 앞으로 의식하면서 계속 사용해야겠다.

 

 

코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        String str = br.readLine();
        long[] arr = new long[str.length() + 1];

        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) == '<') {
                arr[i + 1] = Math.max(arr[i + 1], arr[i] + 1);
            }
        }

        for (int i = str.length() - 1; i >= 0; i--) {
            if (str.charAt(i) == '>') {
                arr[i] = Math.max(arr[i], arr[i + 1] + 1);
            }
        }

        bw.write(Arrays.stream(arr).sum() + "");

        bw.flush();
        bw.close();
        br.close();
    }
}

 

 

4. B - ss

 

코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        String str = br.readLine();
        int ans = 0;
        for (int len = 2; len < str.length(); len += 2) {
            for (int i = 0; i + len - 1 < str.length(); i++) {
                String left = str.substring(i, i + len / 2);
                String right = str.substring(i + len / 2, i + len);
                if (left.equals(right)) ans = len;
            }
        }

        bw.write(ans + "");

        bw.flush();
        bw.close();
        br.close();
    }
}

 

 

5. D - ModSum

 

풀이

 (1 mod 2) + (2 mod 3) + ... + (N-1 mod N) + (N mod 1)이 되도록 하는 게 최선이다. 어떤 permutation 값을 바꾸든 기존 값보다 적어진다는 것을 보여주면 된다.

 

 케이스를 마지막 번재 값과 다른 어느 값을 바꾸는 경우, 마지막 번째를 제외한 나머지 중 어느 두 값을 바꾸는 경우로 나눌 수 있다.

 - 마지막 번째 제외

 i < j라 하자. 그럼 x_i = i + 1이고 x_j = j + 1이다. (j mod (i + 1)) + (i mod (j + 1)) <= i + i < i + j = (i mod (i + 1)) + (j mod (j + 1))이므로 반드시 손해를 본다.

 

 - 마지막 번째를 포함

(i mod 1) + (N mod (i + 1)) = (N mod (i + 1)) <= i = (i mod (i + 1)) + (N mod 1)이므로 서로 바꿔도 이득을 얻진 않는다.

 

 따라서 기존의 방식은 최적이며, 정답은 1 ~ N - 1까지의 합이다.

 

 

개선

 - Even인지 판단하는 부분을 짤 때, 지원해주는 라이브러리를 사용하지 않고 일일이 구현했다. 문자열에 관한 문제는 기본으로 제공해주는 라이브러리를 잘 활용할 수 있도록 의식해야 된다.

 

 

코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        long n = Integer.parseInt(br.readLine());
        long ans = (n - 1) * n / 2;

        bw.write(ans + "");

        bw.flush();
        bw.close();
        br.close();
    }
}