안경잡이개발자

728x90
반응형

대회 링크: codeforces.com/contest/1436

A번 문제: codeforces.com/contest/1436/problem/A

 

  아래 식이 의미하는 내용은 a1 + a2 + ... + an이다. 시그마가 중첩되어 작성되어 있어서 헷갈릴 수 있지만, 식을 나열해보면 그렇다. 다시 말해 그냥 모든 원소의 합이 M과 같다면 "YES", M과 다르다면 "NO"를 출력하면 된다.

 

 

for _ in range(int(input())):
    n, m = map(int, input().split())
    data = list(map(int, input().split()))

    # 모든 원소의 합이 M인 경우 "YES" 출력
    if sum(data) == m:
        print("YES")
    else:
        print("NO")

 

B번 문제: codeforces.com/contest/1436/problem/B

 

  이 문제는 원소로 0을 사용할 수 있다는 점을 생각하면 매우 쉽다. 1을 2개 쓰고, 나머지를 0으로 채우면 된다. 이후에 각 줄마다 시프트(shift)를 하면서 출력하면 된다. 예를 들어 N = 4일 때는 다음과 같이 만들면 된다.

 

for _ in range(int(input())):
    n = int(input())
    arr = [1, 1] + [0] * (n - 2)
    arr = arr + arr

    for i in range(n):
        for j in range(i, n + i):
            print(arr[j], end=' ')
        print()

 

  사실 나는 이 문제를 푸는 당시에는 N이 100 이하라서 에라토스테네스의 체를 이용해 N = 100까지의 모든 경우에 대하여 사전에 계산하는 방식을 이용했다. 아무튼 제일 쉬운 방법은 그냥 0과 1로 배열을 채우는 것이다.

 

C번 문제: codeforces.com/contest/1436/problem/C

 

  예시로 n = 6, x = 3, pos = 1이라고 해보자. 그러면 다음과 같이 3은 항상 인덱스(index) 1에 위치할 것이다. 이때 주어진 알고리즘에 맞게 그대로 시뮬레이션하면 된다. 일단 시작 단계는 다음과 같을 것이다.

 

 

  이후에 중간점(mid)을 확인한다. 향후 중간점의 왼쪽 부분을 탐색해야 하므로, 중간점(mid)에 위치한 값은 x보다 큰 값이 되어야 한다.

 

 

  이후에 마찬가지로 중간점(mid)을 확인하는데, x를 찾은 것을 알 수 있다. 여기에서 중요한 점주어진 알고리즘에 따르면 여기에서 알고리즘을 종료하지 않고 계속해서 탐색을 진행한다는 것이다. 이 부분을 놓치면 오답 판정을 받게 된다.

 

 

  다음 단계에서도 중간점(mid)을 확인한다. 여기에서 중간점은 마찬가지로 x보다 큰 수가 되어야 한다.

 

 

  이 예시에서의 정답은 (3보다 큰 수의 개수에서 2개를 뽑는 순열의 수) * 3!이 된다. 다시 말해 정답은 36이다. 이러한 원리를 그대로 코드로 옮겨 구현하면 다음과 같다.

 

MOD = int(1e9 + 7)

n, x, pos = map(int, input().split())

under_cnt = x - 1
over_cnt = n - x

under = 0
over = 0
 
left = 0
right = n

while left < right:
    middle = (left + right) // 2
    if middle < pos:
        left = middle + 1
        under += 1
    elif middle > pos:
        right = middle
        over += 1
    # (핵심) middle == pos일 때에도 멈추지 않음
    else:
        left = middle + 1

if under > under_cnt or over_cnt < over:
    print(0)
else:
    answer = 1
    # Permutation(under_cnt, under)
    for i in range(under):
        answer = (answer * (under_cnt - i)) % MOD
    # Permutation(over_cnt, over)
    for i in range(over):
        answer = (answer * (over_cnt - i)) % MOD
    # 남은 수들에 대해서도 Permutation 돌리면 정답
    for i in range(1, n - under - over):
        answer = (answer * i) % MOD
    print(answer)
728x90
반응형

Comment +0

728x90
반응형

대회 링크: codeforces.com/contest/1421

A번 문제: codeforces.com/contest/1421/problem/A

 

 문제 제목이 정답이다. 단순히 a xor b를 출력하면 정답이 된다.

 

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    int testCase;
    cin >> testCase;
    for (int tc = 0; tc < testCase; tc++) {
        unsigned int a, b;
        cin >> a >> b;
        cout << (a ^ b) << '\n';
    }
}

 

B번 문제: codeforces.com/contest/1421/problem/B

 

  이 문제는 S와 F의 위치에서 인접한 2칸씩만 확인하면 된다. 아래 그림에서 색칠한 부분이 이에 해당한다. 이 아이디어를 떠올릴 수 있으면 문제를 해결할 수 있다.

 

 

C번 문제: codeforces.com/contest/1421/problem/C

 

  이 문제에서는 두 가지의 연산을 허용한다.

 

  ① L 연산

 

  쪽에서 두 번째 인덱스부터 i까지의 문자열뒤집어 왼쪽에 붙이는 연산

 

 

  ② R 연산

 

  오른쪽에서 두 번째 인덱스부터 i까지의 문자열뒤집어 오른쪽에 붙이는 연산

 

 

  이것저것 생각하다 보면 다음의 세 연산으로 정답 판정을 받을 수 있다는 것을 알 수 있다.

 

data = input()
n = len(data)

print(3)
print("L", n - 1)
print("R", n - 1)
print("R", 2 * n - 1)

 

  예시를 들어 그리자면 다음과 같다.

 

  ※ 첫 번째 연산 ※

 

 

  ※ 두 번째 연산 ※

 

 

  ※ 세 번째 연산 ※

 

 

D번 문제: codeforces.com/contest/1421/problem/D

 

  이 문제는 대략 다음과 같은 코드로 정답 판정을 받을 수 있다. 먼저 6가지 방향에 대해서 최소 거리를 계산한 뒤에, 실제로 6가지 이동 연산을 이용하여 목표 지점까지의 최소 거리를 출력하면 정답이다.

 

for _ in range(int(input())):
    x, y = map(int, input().split())
    c1, c2, c3, c4, c5, c6 = map(int, input().split())
 
    # 6가지 방향에 대한 이동 거리 최적화
    c1 = min(c1, c2 + c6)
    c2 = min(c2, c1 + c3)
    c3 = min(c3, c2 + c4)
    c4 = min(c4, c3 + c5)
    c5 = min(c5, c4 + c6)
    c6 = min(c6, c1 + c5)
    
    # 최단 경로 계산하기
728x90
반응형

Comment +0

728x90
반응형

  코드포스(Codeforces) 웹 사이트 내에서 점수 변화 및 퍼포먼스(performance) 정보도 함께 확인하고자 한다면, 캐럿(Carrot) 확장 프로그램을 사용할 수 있습니다. 캐럿을 사용하면 다음과 같이, 내가 오늘 치른 대회에서의 퍼포먼스(performance)점수 변화량(delta)을 확인할 수 있습니다.

 

 

  ▶ 캐럿(Carrot) 확장 프로그램 다운로드

 

 

Carrot

Rating predictor for Codeforces

chrome.google.com

 

  사이트에 접속한 뒤에 [Chrome에 추가] 버튼을 눌러서 설치하시면 됩니다.

 

 

  설치 이후에 크롬(Chrome) 브라우저에서 사용 설정을 하시면 곧바로 코드포스 사이트에 접속해서 이용하실 수 있습니다.

728x90
반응형

Comment +0

728x90
반응형

대회 링크: codeforces.com/contest/1408

A번 문제: codeforces.com/contest/1408/problem/A

 

  세 개의 수열(Sequence) a, b, c가 존재한다. 이때 수열의 길이는 모두 n으로 동일하다. 또한 각 인덱스에 따른 ai, bi, ci는 서로 다르다. 이때 다음의 조건을 만족하는, 길이가 n인 수열 p를 하나라도 찾으면 된다.

 


[ 문제 해설 ]

 

  기본적으로 ai, bi, ci가 서로 다르다는 조건이 있다. 따라서 일단 a[0]를 출력한 뒤에 그다음부터는 그리디(greedy)하게 하나씩 출력하면 된다. 이때 (순환적으로) 인접한 두 수가 서로 달라지도록 하면 된다. 매번 바로 이전에 출력했던 수를 제외하고 다른 수를 하나 출력하도록 하자. 단, 마지막 수를 출력할 때는 첫째 수 또한 제외하고 출력해야 한다.

 

[ 정답 코드 ]

 

for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    c = list(map(int, input().split()))

    # 첫 번째 수 출력
    now = a[0]
    print(now, end=' ')

    # n - 2개의 수 출력
    for i in range(1, n - 1):
        if now != a[i]:
            now = a[i]
        elif now != b[i]:
            now = b[i]
        elif now != c[i]:
            now = c[i]
    print(now, end=' ')
    
    # 마지막 수 출력
    if now != a[n - 1] and a[n - 1] != a[0]:
        now = a[n - 1]
    elif now != b[n - 1] and b[n - 1] != a[0]:
        now = b[n - 1]
    elif now != c[n - 1] and c[n - 1] != a[0]:
        now = c[n - 1]
    print(now)

 

B번 문제: codeforces.com/contest/1408/problem/B

 

  길이가 n0 이상(non-negative)의 정수로 구성된 비내림차순(non-decreasing) 배열 a가 있다. 우리는 m개의 0 이상(non-negative)의 정수로 구성된 비내림차순(non-decreasing) 배열의 집합 b를 찾는 것이다. 또한 k 값이 입력으로 주어진다. 이때 다음과 같은 조건을 만족하는 가장 작은 m을 찾으면 된다.

 

 

[ 문제 해설 ]

 

  이 문제는 테이블 형태로 그려보면 아이디어를 쉽게 찾을 수 있다. 예를 들어 n = 9, k = 4라고 하자.

 

  a = [0, 1, 2, 2, 3, 3, 3, 4, 4, 4, 4]라고 하면 다음과 같은 수열 b들을 찾을 수 있다.

 

  2 2 3 5 7 11 13 13 17
b1 2 2 3 5 7 7 7 7 7
b2 0 0 0 0 0 4 6 6 10

 

  결과적으로 m의 최솟값은 2이다. 문제 해결 아이디어는 간단하다. 먼저 배열 a에서 서로 다른 원소의 개수를 cnt라고 하자. 이때 cnt를 줄여나가는 방식을 사용한다. b1은 항상 k개만큼의 cnt를 줄일 수 있다. 이후에 b2부터 모든 배열은 (k - 1)개 만큼의 cnt를 줄일 수 있다.

 

[ 정답 코드 ]

 

import math

for _ in range(int(input())):
    n, k = map(int, input().split())

    # 서로 다른 원소 개수
    cnt = len(set(map(int, input().split())))

    if cnt > 1 and k == 1: # (k - 1)이 0이므로 만들 수 없는 경우
        print(-1)
    elif cnt <= k:
        print(1)
    else:
        print(1 + math.ceil((cnt - k) / (k - 1)))

 

C번 문제: codeforces.com/contest/1408/problem/C

 

  길이가 l인 도로가 있다. 이 도로는 좌표 0부터 l까지의 정수로 구성된다. 왼쪽 차는 0에서 시작해서 오른쪽으로 간다. 오른쪽 차는 l에서 시작해서 왼쪽으로 간다. 처음 두 자동차의 속력은 1/s이다. 그리고 n개의 깃발(flag)이 존재한다. 두 자동차는 깃발을 지날 때마다 속력이 1/s씩 증가한다.

 

  결과적으로 두 자동차가 만나는 시간을 출력하면 된다.

 

[ 문제 해설 ]

 

  예를 들어 l = 7이고, 다음과 같이 5개의 깃발이 있다고 해보자.

 

0 1 2 3 4 5 6 7
왼쪽 차 깃발(flag) 깃발(flag) 깃발(flag) 깃발(flag)   깃발(flag) 오른쪽 차

 

  아이디어는 간단하다. 총 n개의 깃발(flag)을 확인하면 된다. 다시 말해 n번을 반복하는데, 반복할 때마다 매번 ① 왼쪽 차 기준으로 다음 깃발까지의 남은 시간, ② 오른쪽 차 기준으로 다음 깃발까지의 남은 시간을 계산하자. 이때 시간이 더 짧은 쪽이 해당 깃발까지 이동하도록 만들면 된다. 그 시간 동안 상대방 차 또한 이동하도록 만들면 된다. 결과적으로 n개의 깃발을 다 처리한 뒤에, 두 자동차가 만나기 위해 걸리는 시간까지 계산해 더해주면 된다.

 

  거리 = 속도 X 시간

 

  위와 같은 공식(거속시)을 이용하여 코드를 작성하면 다음과 같다.

 

[ 정답 코드 ]

 

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    int testCase;
    cin >> testCase;
    for (int tc = 0; tc < testCase; tc++) {
        int n, l;
        cin >> n >> l;

        // n개의 깃발(flag) 정보 입력받기
        vector<int> data;
        for (int i = 0; i < n; i ++) {
            int x;
            cin >> x;
            data.push_back(x);
        }

        // 처음 A와 B의 정보 초기화
        long double aPos = 0;
        int aNext = 0;
        int aSpeed = 1;

        long double bPos = l;
        int bNext = n - 1;
        int bSpeed = 1;

        // A와 B가 만나기까지 걸리는 총 시간(time)
        long double time = 0.0;

        // n개의 깃발에 대하여 하나씩 처리
        int cnt = 0;
        while (cnt != n) {
            // A와 B의 다음 깃발까지의 거리
            long double aDistance = data[aNext] - aPos;
            long double bDistance = bPos - data[bNext];

            // A와 B의 다음 깃발까지의 시간
            long double aTime = aDistance / aSpeed;
            long double bTime = bDistance / bSpeed;

            // 더 짧은 시간이 걸리는 자동차를 기준으로 이동
            if (aTime <= bTime) {
                aPos = data[aNext];
                bPos -= aTime * bSpeed;
                aNext += 1;
                aSpeed += 1;
                time += aTime;
            }
            else {
                bPos = data[bNext];
                aPos += bTime * aSpeed;
                bNext -= 1;
                bSpeed += 1;
                time += bTime;
            }
            cnt++;
        }

        // 마지막으로 A와 B가 서로 만나도록 하기
        long double distance = bPos - aPos;
        time += distance / (aSpeed + bSpeed);

        cout.precision(15);
        cout << fixed;
        cout << time << '\n';
    }
}

 

D번 문제: codeforces.com/contest/1408/problem/D

 

[ 정답 코드 ]

 

n, m = map(int, input().split())

robbers = []
lights = []

for i in range(n):
    a, b = map(int, input().split())
    robbers.append((a, b))

for i in range(m):
    c, d = map(int, input().split())
    lights.append((c, d))

v = [0] * 1000002

for a, b in robbers:
    for c, d in lights:
        # 현재 robber보다 light의 x가 더 크거나 같다면 감시 가능
        if a <= c:
            # 그때 robber가 y 방향으로 얼마만큼 이동해야 숨을 수 있는지 계산
            v[c - a] = max(v[c - a], d - b + 1)

result = 1000001 # 1000001만큼 움직이는 것이 최악의 경우
dy_max = 0 # 가장 큰 dy 값

# 1000001부터 0까지 1씩 줄여가며, 모든 dx에 대하여
for dx in range(1000001, -1, -1):
    dy_max = max(dy_max, v[dx])
    # (dx + dy_max) 값이 가장 작은 경우를 출력
    result = min(result, dx + dy_max)

print(result)
728x90
반응형

Comment +0

728x90
반응형

대회 링크: codeforces.com/contest/1407

A번 문제: codeforces.com/contest/1407/problem/A

 

  이 문제는 0 혹은 1로만 구성된 수열이 주어졌을 때, 순서를 유지한 상태로 최대 N / 2개의 원소를 삭제해서 다음의 식이 성립하도록 만들어야 한다. (N은 항상 2의 배수)

 

  a1 - a2 + a3 - a4 + ... = 0

 

[ 문제 해설 ]

 

  이 문제의 해결 아이디어는 꽤 간단하다. 먼저 수열에 들어 있는 0과 1의 개수를 각각 계산한다.

 

  ① 만약 0의 개수가 더 많거나 같다면 0의 개수만큼 출력하면 된다. ② 만약 1의 개수가 더 많다면 1의 개수만큼 출력해야 한다. 단, 1의 개수가 홀수인 경우에는 1개 적은 만큼 출력해야 한다.

 

  예를 들어 [1, 0, 1, 0, 0, 0]이 들어왔을 때에는 [0, 0, 0, 0]을 출력하면 된다. [1, 0, 1, 1, 1, 0]이 들어왔을 때에는 [1, 1, 1, 1]을 출력하면 된다.

 

[ 정답 코드 ]

 

for _ in range(int(input())):
    n = int(input())
    data = list(map(int, input().split()))
    zero = 0
    one = 0
    for x in data:
        if x == 0:
            zero += 1
        else:
            one += 1
    if zero >= one:
        print(zero)
        for i in range(zero):
            print(0, end=' ')
    else:
        print(one // 2 * 2) # 홀수인 경우 1이 더 작은 수를 이용
        for i in range(one // 2 * 2):
            print(1, end=' ')
    print()

 

B번 문제: codeforces.com/contest/1407/problem/B


  이 문제는 N개의 양의 정수를 담은 수열 a1, a2, a3, ..., an이 있을 때, 원소를 하나씩만 사용해서 수열 b1, b2, b3, ..., bn를 만드는 문제다. 이때 ci = GCD(b1, ..., bi)라고 하자. 우리는 수열 c1, c2, c3, ..., cn이 사전적으로 최댓값을 가지도록 하고 싶다.

 

  예를 들어 수열 A = {64, 25, 75, 100, 50}라고 하면, 정답 수열 B = {100, 50, 25, 75, 64}를 찾을 수 있다.

 

[ 문제 해설 ]

 

  이 문제는 완전 탐색으로 해결할 수 있다. 그냥 이중 반복문을 돌리면서 Maximum을 찾으면 된다. 다만, GCD(x, y, z) = GCD(GCD(x, y), z)라는 점을 알고 있어야 한다. 또한 0은 모든 정수의 배수라는 점에서 GCD(0, x) = x라는 점을 기억하자. 사실 이는 잘 알려진 공식이므로 이를 이용하여 쉽게 문제를 해결할 수 있다. 참고로 GCD 함수는 로그 복잡도를 가지므로 빠르게 동작한다.

 

[ 정답 코드 ]

 

import math
 
for _ in range(int(input())):
    n = int(input())
    data = list(map(int, input().split()))
    gcd_value = 0
    for i in range(n):
        max_value = (0, 0) # (현재 GCD 값, index)를 한꺼번에 묶어서 저장
        for j in range(n):
            if data[j] != -1: # 아직 출력하지 않은 데이터 중에 GCD 값을 가장 크게 만드는 데이터 찾기
                max_value = max(max_value, (math.gcd(gcd_value, data[j]), j))
        gcd_value = max_value[0] # GCD 값 갱신
        print(data[max_value[1]], end=' ') # 해당 데이터 출력
        data[max_value[1]] = -1 # 해당 데이터 처리 완료
    print()

 

C번 문제: codeforces.com/contest/1407/problem/C


  이 문제는 1부터 N까지의 값을 하나씩 가지고 있는 하나의 순열(Permutation)을 찾는 문제다. 우리는 최대 2 * N만큼의 쿼리를 날려서 정보를 얻어올 수 있다.

 

  이때 ? i j라고 쿼리를 날리면, pi mod pj의 값을 알려준다.

 

[ 문제 해설 ]

 

  나도 이 문제를 풀면서 떠올리게 된 사실인데, 두 양의 정수가 있을 때 쿼리를 두 번 날리면 누가 더 큰 지를 알 수 있다. 예를 들어 서로 다른 양의 정수 x와 y가 있을 때 다음의 명제가 성립한다.

 

  x mod y > y mod x라면, ① x보다 y가 더 크며 ② x mod y = x이다.

 

  따라서 앞에서부터 두 수씩 묶어서 쿼리를 날려 본다. 쿼리를 날리면서 항상 몇 번째 수가 가장 큰 지를 저장하면서, 우리는 더 작은 수의 값을 매번 확실히 찾을 수 있다.

 

import sys
 
n = int(input())
 
answers = [-1] * (n + 1)
 
max_index = 1
next_index = 2
 
for i in range(n - 1):
    print("?", max_index, next_index)
    sys.stdout.flush()
    one = int(input())
    print("?", next_index, max_index)
    sys.stdout.flush()
    two = int(input())
    if one < two:
        answers[next_index] = two
    else:
        answers[max_index] = one
        max_index = next_index
    next_index += 1
 
answers[max_index] = n
 
print("!", end=' ')
for i in range(1, n + 1):
    print(answers[i], end=' ')
728x90
반응형

Comment +0

728x90
반응형

대회 링크: https://codeforces.com/contest/1352

A번 문제: https://codeforces.com/contest/1352/problem/A

 

[ 문제 해설 ]

 

  이 문제는 먼저 각 자릿수를 확인하면 된다. 이 때, 0이 아닌 자릿수에 대하여 그 값들을 출력해주면 된다. 예를 들어 입력이 6009이라면, 6000과 9를 출력하면 된다. 소스코드는 다음과 같다.

 

[ 정답 코드 ]

 

for _ in range(int(input())):
    n = int(input())
    result = []

    power = 1
    # 각 자릿수를 확인하며
    while n > 0:
        # 0이 아닌 자릿수에 대하여
        if n % 10 != 0:
            # 그 값들을 각각 출력
            result.append((n % 10) * power)
        n //= 10
        power *= 10
  
    print(len(result))
    for i in result:
        print(i, end=' ')
    print()

 

B번 문제: https://codeforces.com/contest/1352/problem/B


  이 문제는 k개의 수를 더해서 n을 만들 수 있는지 물어보는 문제이다. 단, k개의 수는 모두 홀수이거나 모두 짝수여야 한다.

[ 문제 해설 ]

 

  문제에서 요구하는 대로 모든 수가 홀수이거나, 모든 수가 짝수인 경우 두 가지만 고려하면 된다.

  먼저 모든 수가 홀수인 경우, (k - 1)개의 수를 모두 1로 설정(가능한 작은 수)한 뒤에  '나머지 1개의 수'홀수이면서 조건을 만족시킬 수 시 있는지 확인하면 된다.  예를 들어 n = 7, k = 5인 경우에는 (k - 1) + 3 = 7로 n을 만족시킬 수 있다. 즉, 나머지 1개의 수를 3으로 설정하면 된다.

  그리고 모든 수가 짝수인 경우, (k - 1)개의 수를 모두 2로 설정(가능한 작은 수)한 뒤에  '나머지 1개의 수'짝수이면서 조건을 만족시킬 수 있는지 확인하면 된다. 예를 들어 n = 8, k = 3인 경우에는 (k - 1) * 2 + 4 = 8로 n을 만족시킬 수 있다. 즉, 나머지 1개의 수를 4로 설정하면 된다.

  따라서 두 가지 경우만 잘 고려해주는 코드를 작성하면 된다.

 

[ 정답 코드 ]

 

for _ in range(int(input())):
    n, k = map(int, input().split())

    # 모든 수가 홀수인 경우
    odd = n - (k - 1)
    if odd > 0 and odd % 2 == 1:
        print("YES")
        for i in range(k - 1):
            print(1, end=' ')
        print(odd)
        continue

    # 모든 수가 짝수인 경우
    even = n - (k - 1) * 2
    if even > 0 and even % 2 == 0:
        print("YES")
        for i in range(k - 1):
            print(2, end=' ')
        print(even)
        continue

    # 두 가지 케이스 모두 만족시킬 수 없을 때
    print("NO")

 

C번 문제: https://codeforces.com/contest/1352/problem/C


  n과 k가 주어졌을 때, n으로 나누어 떨어지지 않는 k번째 자연수를 찾으면 되는 문제다. 

 

  예를 들어 n = 3, k = 7이라고 하면

 

  1, 2, 4, 5, 7, 8, 10, 11, 13, ... 

  위와 같이 이어지므로, 7번째 수는 바로 10이 된다.

[ 문제 해설 ]

 

  답을 구하는 방법은 생각보다 쉽다. 구하고자 하는 k번째 자연수는 항상 k 이상이고, 그리고 2k 미만이 된다.

 

  생각해 보면, n = 2일 때는 1, 3, 5, 7, ... 이렇게 갈 텐데, 이 때에도 k번째 수는 2k보다 작은 2k - 1이 된다. 다시 말해 출력해야 되는 정답은 항상 k 이상 2k 미만의 수가 될 것이다. 그렇다면 k보다 얼마나 큰 수가 출력되어야 하는가?

 

  그것은 바로 k보다 (k - 1) // (n - 1)만큼만 커지면 된다. 즉, k + (k - 1) // (n - 1)이 정답이다. 답을 계산하는 방법은 굉장히 다양하지만, 이것보다 간단히 수식으로 표현할 수 있는 답은 없다.

 

[ 정답 코드 ]

 

for _ in range(int(input())):
    n, k = map(int, input().split())
    print(k + (k - 1) // (n - 1))

 

D번 문제: https://codeforces.com/contest/1352/problem/D

 

  왼쪽에서부터 오른쪽으로 과자를 먹는 사람과 오른쪽에서부터 왼쪽으로 과자를 먹는 사람이 있다. 

  이 때 한 차례씩 반복하면서 먹어나가는데, 이전 차례에서 상대방이 먹었던 양보다 더 많이 먹어야 하는 방식이다. 그래서 전체 몇 차례나 반복되었는지, 두 사람이 각각 얼마나 먹었는지를 출력하면 된다.

 

[ 문제 해설 ]

 

  이 문제는 문제에서 요구하는 대로 구현만 잘 해주면 된다. 최대한 깔끔하게 실수 없이 구현해서 정답 처리를 받으면 된다.

 

[ 정답 코드 ]

 

for _ in range(int(input())):
    n = int(input())
    data = list(map(int, input().split()))
    l = 0
    r = n - 1
    left_sum, right_sum = 0, 0
    left_res, right_res = 0, 0
    count = 0

    # 일종의 투 포인터(Two Pointers) 기법
    while l <= r:
        # 왼쪽에서 먹을 차례
        if count % 2 == 0:
            now_sum = 0
            while l <= r and now_sum <= right_sum:
                now_sum += data[l]
                l += 1
            left_res += now_sum
            left_sum = now_sum
        # 오른쪽에서 먹을 차례
        elif count % 2 == 1:
            now_sum = 0
            while l <= r and now_sum <= left_sum:
                now_sum += data[r]
                r -= 1
            right_res += now_sum
            right_sum = now_sum
        count += 1

    print(count, left_res, right_res)

 

E번 문제: https://codeforces.com/contest/1352/problem/E

 

  n개의 정수로 구성된 수열이 있을 때, 각 n개의 수에 대하여 그 수와 동일한 합을 가지는 '부분 연속 수열'이 존재하는지 찾으면 되는 문제이다.

  예를 들어 [3, 1, 4, 1, 5, 9, 2, 6, 5]가 있을 때 6번째 수인 9는 [3, 1, 4, 1]의 합과 같다.

 

[ 접근 방법 1 ]


  일단 이 문제는 투 포인터(Two Pointer)를 이용하여 해결할 수 있다. n개의 수 각각에 대하여 투 포인터 알고리즘을 돌리면 된다. 투 포인터 문제로 유명한 '합이 M인 부분 연속 수열 찾기' 코드를 그대로 쓰면 된다.

  단, 이 문제에서는 부분 연속 수열의 길이가 2 이상이 되라고 하였으므로 투 포인터 알고리즘을 길이가 2 이상인 경우만 찾도록 수정해서 이용하면 된다.

  코드포스 문제를 풀다 보면, 투 포인터 문제가 굉장히 자주 나오는 것 같다. 혹은... 내가 그냥 해법으로 투 포인터를 먼저 생각해서 그러는 거일 수도 있겠다. 근데 이게 가끔은 시간 초과를 받는 경우도 있으니 조심해야 한다.

 

for _ in range(int(input())):
    n = int(input())
    data = list(map(int, input().split()))
    result = 0

    for x in data:
        summary = 0
        end = 0

        for start in range(n):
            while summary < x and end < n:
                summary += data[end]
                end += 1
            if summary == x and end - start >= 2:
                result += 1
                break
            summary -= data[start]

    print(result)

 

  근데... 걱정했던 대로 위 코드는 시간초과를 받았다. 투 포인터를 이용할 때에도 사실 O(N^2)의 해법으로 시간 복잡도가 똑같기 때문에 괜찮을 줄 알았는데, 파이썬을 이용하고 있기 때문인지... 시간 초과를 받을 줄은 몰랐다. ㅠㅠ 시간 초과를 받은 케이스를 보니까 정말 간발의 차이로 시간 초과를 받았다. 0.5초만 더 널널했어도, 시간 초과를 받지 않았을 것 같다.

 

[ 접근 방법 2 ]

 

  아무튼 같은 O(N^2)이지만, 조금 더 빠른 해법은 모든 구간의 합을 하나의 배열에 기록해 놓는 방법이다. (계수 정렬 할 때 처럼) 모든 값들이 n (1 <= n <= 8000) 보다 작기 때문에 이 또한 가능하다. 시간 초과에 걸리지 않는, 정답 코드는 다음과 같다.

 

[ 정답 코드 ]

 

for testcase in range(int(input())):
    n = int(input())
    data = list(map(int, input().split()))

    # 모든 구간 합을 저장하기 위한 집합 자료형
    visited = set()

    # 길이가 2 이상인 모든 구간 합을 집합에 저장
    for i in range(n):
        summary = data[i]
        for j in range(i + 1, n):
            summary += data[j]
            if summary > n:
                break
            visited.add(summary)

    # 각 값을 확인하며, 계산할 수 있는 구간 합인 경우 카운트
    result = 0
    for x in data:
        if x in visited:
            result += 1

    print(result)

 

F번 문제: https://codeforces.com/contest/1352/problem/F

 

[ 문제 해설 ]


  이 문제도 구현 문제인데, 최대한 구현 실수가 발생하지 않게 깔끔한 아이디어로 푸는 것이 중요하다. 일단 가장 중요한 게 n1 = 0인 케이스이다. 이 때는 n0과 n2 둘 중에 하나는 0이 되어야 한다. 안 그러면 조건이 만족되지 않는다. 따라서 n1 = 0인 경우에는, 단순히 n0과 n2 중에 하나만 0이 아닌 값을 가진다는 것을 고려해서 풀면 된다.

  그리고 n1 = 0인 케이스가 아니라면, 다음과 같이 먼저 처리해서 문제를 해결할 수 있다.

  해결법은 바로 다음과 같다. 먼저 (n2 + 1)의 크기만큼 1을 출력한다. 그리고 n0의 크기만큼 0을 출력한다. 이후에 n1의 크기만큼 010101... 을 반복해서 출력하면 된다. 그러면 정확히 조건을 만족할 수 있다.

 

[ 정답 코드 ]

 

for testcase in range(int(input())):
    n0, n1, n2 = map(int, input().split())
    
    # n1가 0인 특이 케이스 처리
    if n1 == 0:
        if n0 > 0:
            print("0" * (n0 + 1))
        else:
            print("1" * (n2 + 1))
        continue

    # 일반적인 케이스 처리
    print("1" * (n2 + 1), end="")
    print("0" * n0, end="")
    for i in range(n1):
        if i % 2 == 0:
            print("0", end="")
        else:
            print("1", end="")
    print()

 

G번 문제: https://codeforces.com/contest/1352/problem/G

 

[ 문제 해설 ]


  이 문제도 간단한 아이디어를 떠올리면 간단히 풀 수 있다. 필자는 대회 당시에는 매우 복잡하게 푼 것 같은데, 실제로는 매우 간단하게도 문제를 해결할 수 있었다.

  홀수를 먼저 내림차순으로 출력한 뒤에 4와 2를 출력하고, 다시 모든 짝수를 오름차순으로 차례대로 출력하면 된다. 이렇게 대칭을 이루도록 출력하면 간단하게 해결된다.

  예를 들어 n = 11이라고 하면,

  [ 11 9 7 5 3 1 ] [ 4 2] [6 8 10]로 출력하면 된다.

  위 출력 결과를 보면 인접한 모든 수들은 2 이상, 4 이하로 차이가 난다.

 

[ 정답 코드 ]

 

for _ in range(int(input())):
    n = int(input())
    # 4보다 작은 경우, 만들 수 없음
    if n < 4:
        print(-1)
        continue
  
    # 모든 홀수를 먼저 내림차순으로 출력
    for i in range(n, 0, -1):
        if i % 2 == 1:
            print(i, end=' ')
    # 4와 2를 출력
    print(4, 2, end=' ')
    # 모든 짝수를 오름차순으로 출력
    for i in range(6, n + 1, 2):
        print(i, end=' ')
    print()

 

728x90
반응형

Comment +0