안경잡이개발자

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

728x90
반응형

  코드포스의 경우 다른 사람의 소스코드를 해킹(Hack)할 수 있는 기능이 제공된다. 사실 처음에는 알고리즘 대회인데 해킹 시스템이 왜 있는지 궁금했다. 해킹은 다른 사람의 소스코드를 지적하는 의미가 되기도 하고, 알고리즘 대회 자체가 가지고 있는 채점 데이터 셋의 오류를 지적하는 의미가 되기도 한다.

 

  일단 코드포스에서는 대회 도중에 해킹(Hacking)하는 경우와, 대회가 끝난 뒤에 12시간 동안 오픈 해킹(Open Hacking)을 하는 경우가 있다. 방법은 기본적으로 유사하다. 일단 상대방의 소스코드를 확인한 뒤에 문제가 있다고 판단이 되면, 소스코드에서 제대로 처리하지 못할 입력(Input)을 만들어서 입력하면 된다.

 

  내 코드를 잠금(Lock) 했거나, 오픈 해킹 기간일 때는 다음과 같이 다른 사람들의 소스코드를 확인할 수 있다. 기간 안에는 이러한 소스코드에 해킹을 시도할 수 있다.

 

 

  다른 사람의 소스코드를 확인한 뒤에 [hack it!] 버튼을 눌러서 해킹을 시도하면 된다.

 

 

  해킹을 시도할 때는 입력 문자열을 직접 넣거나, 입력 문자열이 담긴 파일을 업로드해서 제출하면 된다.

 

 

  나는 한 번 자핵을 해보았다. 내가 낸 소스코드에 문제가 있는 것 같아서, 오픈 해킹 기간 때 내 소스코드를 직접 공격해보았다. 아무튼 해킹에는 성공했다.

 

  해킹에 성공한 경우 다음과 같이 "Successful hacking attempt"라는 메시지가 나온다. 해킹에 실패한 경우 "Unsuccessful hacking attempt"라고 나오며, 입력 자체가 잘못된 경우에는 "Invalid input"이라는 메시지가 나온다.

 

 

  해킹에 성공한 경우, 해킹을 당한 쪽은 다음과 같은 메시지가 출력된다.

 

 

  다음과 같이 스탠딩(Standing)에서는 "해킹 성공 횟수 : 해킹 실패 횟수" 정보가 출력된다.

 

 

  해킹 시스템은 상당히 재미있는 것 같다. 해킹 시스템이 있기 때문에, 채점 데이터셋은 더욱 견고해진다. 실제로 간당간당하게 시간 초과나 메모리 초과를 벗어난 코드들은 채점 데이터가 조금 더 추가되면, 운에 따라서 오답 코드로 처리되기도 한다. 나는 최근에 Pypy로 문제를 풀고 있는데, C++에서는 정답 처리가 될 법한 코드가 가끔씩 TLE를 받기도 한다.

 

[ 해킹용 입력 데이터 만드는 예제 코드 ]

 

import random

f = open("test.txt", 'w')
# The number of test cases
f.write('1\n')
# Input: N
f.write('10000\n')
for i in range(10000):
    # Make random data.
    f.write(str(random.randrange(1, 1001)) + ' ')
f.close()
728x90
반응형

Comment +0

728x90
반응형

문제 유형: 정수론

문제 URL: https://codeforces.com/contest/1055/problem/C


  앨리스(Alice)와 밥(Bob)은 모두 각각 일정한 컨디션 주기가 있습니다. 운이 좋은(Lucky) 날이 몇 일 계속된 이후에, 그 이후에는 운이 나쁜(Unlucky) 날이 몇 일간 계속되는 방식입니다. 이 때 앨리스와 밥이 둘 다 운이 좋은(Lucky) 날이 최대 몇 일 겹칠 수 있는지를 구하면 되는 문제입니다.


  예를 들어 앨리스는 0일부터 2일까지 운이 좋고, 주기가 5라고 가정합시다. 또한 밥은 1일부터 3일까지 운이 좋고, 주기가 5라고 가정합시다. 이 때 운이 좋은 날을 1로, 운이 나쁜 날을 0으로 표현하면 다음과 같습니다. 둘 다 운이 좋은 날은 최대 2일이군요.


  0 1 2 3 4 5 6 7 8 9

  1 1 1 0 0 1 1 1 0 0

  0 1 1 1 0 0 1 1 1 0


  이 문제는 날짜가 0일부터 10억 일까지 입력될 수 있다는 점에서 사실상 상수 시간 안에 답을 도출할 수 있는 알고리즘이 필요합니다. 이는 '특정 주기'로 반복된다는 점에서 조금만 생각해보면 쉽게 구할 수 있습니다.


  바로 앨리스의 주기와 밥의 주기의 최대 공약수(GCD)를 구하는 것입니다. 최대 공약수를 기준으로 앨리스 혹은 밥의 주기를 '슬라이딩'하여 운이 좋은 날이 최대 얼마나 겹치는지 확인할 수 있기 때문이죠. 예를 들어 최대 공약수가 3이 나왔다면, 앨리스 혹은 밥의 컨디션 주기를 3만큼 시프트(Shift) 할 수 있는 것입니다. 왼쪽 혹은 오른쪽으로요. 


  따라서 전체 4가지 경우만 고려하면 돼요.


  1) 좋은 운이 시작되는 날이 A가 B에 비해 먼저 있을 때

  1-1) A가 B의 최대한 왼쪽에 붙는 경우를 계산하기.

  1-2) A가 B의 최대한 오른쪽에 붙는 경우를 계산하기.


  2) 좋은 운이 시작되는 날이 B가 A에 비해 먼저 있을 때

  2-1) B가 A의 최대한 왼쪽에 붙는 경우를 계산하기.

  2-2) B가 A의 최대한 오른쪽에 붙는 경우를 계산하기.


  위 4가지 경우를 모두 고려하여 최대한 많이 겹칠 수 있는 일자를 구하면 됩니다. 따라서 유클리드 알고리즘을 이용하여 사실상 상수에 가까울 정도로 빠른 속도로 답을 도출할 수 있는 것입니다.


※ 입출력 예시 ※

input
Copy
0 2 5
1 3 5
output
Copy
2
input
Copy
0 1 3
2 3 6
output
Copy
1

※ 정답 소스코드 ※

(컴파일 환경: GNU G++11 5.1.0)

#include <iostream>

#include <limits.h>


using namespace std;


int gcd(int a, int b) {

if(a == 0)

return b;

return gcd(b % a, a);

}


int main(void) {

int la, ra, ta, lb, rb, tb;

cin >> la >> ra >> ta >> lb >> rb >> tb;

int pat = gcd(ta, tb);

int res = 0;

int gap = abs(la - lb) / pat;

// a가 b보다 더 앞에 있을 때 

if(la < lb) {

int temp = la + pat * gap; // a가 b의 최대한 왼쪽에 붙는 경우 

res = max(res, (temp + 1 + (ra - la)) - lb); 

temp = la + pat * (gap + 1); // a가 b의 최대한 오른쪽에 붙는 경우 

res = max(res, (1 + rb) - temp); 

}

// b가 a보다 더 앞에 있을 때

else {

int temp = lb + pat * gap; // b가 a의 최대한 왼쪽에 붙는 경우

res = max(res, (temp + 1 + (rb - lb)) - la); 

temp = lb + pat * (gap + 1); // b가 a의 최대한 오른쪽에 붙는 경우 

res = max(res, (1 + ra) - temp);

}

// 두 사람의 운이 좋은 날이 계속되는 길이보다 커질 수는 없음 

res = min(res, rb - lb + 1);

res = min(res, ra - la + 1);

cout << res;

return 0;

}


728x90
반응형

Comment +0

728x90
반응형

문제 유형: 구현

문제 URL: https://codeforces.com/contest/1055/problem/B


  앨리스(Alice)의 머리카락들이 계속 자라고 있습니다. 앨리스는 그래서 미용사에게 찾아갔습니다. 앨리스는 모든 머리카락이 최대 l 센티미터(Centimeter)가 될 수 있도록 머리를 자르고 싶습니다. 앨리스의 머리카락 개수는 N개이며, 각 머리카락을 1번부터 N번까지의 번호로 다룬다고 합시다.


  미용사가 가위를 이용해 한 번 머리카락을 자르면, 미용사는 길이가 l보다 큰 머리카락의 길이를 l이 되도록 만들 수 있습니다. 이 때 머리카락은 1번부터 N번까지 차례대로 위치하며 가위로 서로 인접한 머리카락들을 한 번에 자를 수 있습니다. 미용사는 가능한 빠르게 앨리스의 머리를 손질하고 싶습니다. 미용사가 가위질을 할 때마다 1초가 소요된다고 가정했을 때, 앨리스의 머리를 손질하는 최소 시간을 구하면 되는 문제입니다.


  또한 앨리스는 미용사에게 언제 갈 지를 정확히 결정하지 않았기 때문에, 특정한 시각에 자신의 머리카락의 길이를 미용사에게 알려주면서 머리 손질 시간을 물어보고자 합니다. 이 때 정확히 두 가지 유형의 쿼리(Query)가 있습니다.


  0) 앨리스가 지금 미용사에게 가면 머리를 손질하는데 얼마나 시간이 걸릴 지 물어보는 쿼리입니다.

  1) P와 D가 이어서 입력되며, P번째 머리카락이 D 센티미터만큼 자랐다는 의미를 가지는 쿼리입니다.


  기본적으로 앨리스가 원하는 머리카락 최대 길이인 l은 프로그램이 끝날 때까지 동일한 값을 가진다고 보면 됩니다.


  이 문제는 대표적인 구현 문제 유형이라고 볼 수 있습니다. 또한 인접한 머리카락들을 잘 살펴보는 것이 중요합니다. 그러므로 일단 맨 처음에 주어진 초기 상태를 보고 머리카락을 몇 번 잘라야 하는지를 검사합니다. 이후에 특정한 위치의 머리카락이 길어질 때마다 그 왼쪽과 오른쪽에 있는 머리카락과의 관계를 확인하여, 가위질 횟수가 증가할 지 혹은 감소할 지를 판단하면 됩니다.


  총 9가지 경우의 수만 고려하면 돼요. 머리카락이 l보다 작다가, l보다 길어진 특정한 머리카락의 위치를 (K), 왼쪽과 오른쪽에 있는 머리카락이 각각 길다면 (긴), 짧다면 (짧)이라고 합시다. 또한 머리카락 중에서 K가 가장 왼쪽 혹은 오른쪽에 위치할 때, 끝 부분은 (끝)이라고 합시다.


  1) 짧K짧: K 위치를 잘라야 하므로 가위질 횟수 1 증가

  2) 짧K긴: 오른쪽 가위질에 포함될 수 있으므로 가위질 횟수 그대로

  3) 긴K짧: 왼쪽 가위질에 포함될 수 있으므로 가위질 횟수 그대로

  4) 긴K긴: 왼쪽과 오른쪽 가위질에 모두 포함될 수 있으므로 가위질 횟수 1 감소

  5) 끝K짧: K 위치를 잘라야 하므로 가위질 횟수 1 증가

  6) 끝K긴: 오른쪽 가위질에 포함될 수 있으므로 가위질 횟수 그대로

  7) 짧K끝: K 위치를 잘라야 하므로 가위질 횟수 1 증가

  8) 긴K끝: 왼쪽 가위질에 포함될 수 있으므로 가위질 횟수 그대로

  9) 끝K끝: 원소가 1개인 경우이므로 가위질 횟수 1 증가


  위 9가지 경우의 수를 고려하여 전체 가위질 최소 횟수를 구하는 프로그램을 작성하면 됩니다.


※ 입출력 예시 ※

input
Copy
4 7 3
1 2 3 4
0
1 2 3
0
1 1 3
0
1 3 1
0
output
Copy
1
2
2
1

※ 정답 소스코드 ※

(컴파일 환경: GNU G++11 5.1.0) 

#include <iostream>

using namespace std; long long a[100001]; long long n, m, l; int main(void) { cin >> n >> m >> l; int res = 0; cin >> a[0]; if(a[0] > l) { res++; } for(int i = 1; i < n; i++) { cin >> a[i]; // 초기 상태에서 가위질 횟수를 구합니다. if(a[i] > l) { if(a[i - 1] <= l) { res++; } } } for(int i = 0; i < m; i++) { int oper; cin >> oper; if(oper == 0) { cout << res << '\n'; } else { int x, length; cin >> x >> length; int count = 0; // 머리카락이 l보다 짧았다가, l보다 길어져서 '자를 머리카락'이 되는 경우 if(a[x - 1] <= l && a[x - 1] + length > l) { bool find = false; // 원소가 1개인 경우를 체크하기 위한 목적 if(x - 2 >= 0) { // 왼쪽 머리카락 확인 if(a[x - 2] <= l) count++; // (짧) else count--; // (긴) find = true; } if(x < n) { // 오른쪽 머리카락 확인 if(a[x] <= l) count++; // (짧) else count--; // (긴) find = true; } if(!find) res++; } if(count >= 1) res++; else if(count == -2) res--; a[x - 1] += length; } } return 0; }


728x90
반응형

Comment +0

728x90
반응형

문제 유형: 구현

문제 URL: https://codeforces.com/contest/1055/problem/A


  일직선 형태로 존재하는 지하철 노선이 있다고 합니다. 노선에는 1부터 N까지 번호가 매겨진 N개의 역이 있습니다. 이 때 밥(Bob)은 1번 역에 살고 있으며, 엘리스(Alice)는 S번 역 근처에 살고 있습니다.


  지하철 노선은 두 개의 트랙으로 구성됩니다. 첫 번째 트랙에서는 열차가 역 1에서 역 N으로 이동합니다. 두 번째 트랙에서의 열차는 N부터 1까지 반대 방향으로 이동합니다. 또한 기차는 트랙의 끝에 도달한 순간 운행을 정지한다고 가정합니다.


  다만 일부 역에서는 열차가 멈출 수 없는 상황이라고 합니다. 그러므로 몇몇 역은 열차가 그냥 통과하여 지나간다고 가정합니다. 이러한 상황에서 밥(Bob)에게 각 역에 대해서 열차가 멈출 수 있는지, 없는지의 여부가 알려져 있다고 했을 때 밥이 엘리스의 집으로 갈 수 있는지를 출력하면 됩니다.


  예를 들어 역이 5개이고, 엘리스가 4번 역 근처에 살고 있다고 해봅시다. 이 때 두 개의 트랙에서 열차가 멈출 수 있는 역들은 1로, 멈출 수 없는 역들을 0으로 표현할 때 다음과 같다고 가정합시다.


  첫 번째 트랙: 1 0 0 0 1

  두 번째 트랙: 0 1 1 1 1


  이 때는 밥이 출발지인 1번 역에서 5번 역으로 이동한 뒤에, 5번 역에서 두 번째 트랙을 타고 4번 역으로 이동하여 엘리스의 집에 도착할 수 있습니다.


  이 문제는 정말 간단한 구현 문제입니다. 밥이 항상 1번 역에서 출발한다는 점을 기억하면 됩니다. 그래서 만약 1번 역이 운행되지 않는 상태라면 그 즉시 도달할 수 없음을 알리고 종료하면 됩니다. 이후에는 각 역을 하나씩 확인하며, 첫 번째 트랙에서 운행되는 역일 때만 특정한 조건을 검사하면 됩니다. 여기서 조건은 바로 해당 역이 엘리스가 있는 역인지 혹은 두 번째 트랙으로 이동하여 반대 방향으로 이동하여 엘리스가 있는 역으로 갈 수 있는지를 의미합니다.


  따라서 간단한 난이도의 단순 구현 문제라고 볼 수 있습니다.


※ 입출력 예시 ※

input
Copy
5 3
1 1 1 1 1
1 1 1 1 1
output
Copy
YES
input
Copy
5 4
1 0 0 0 1
0 1 1 1 1
output
Copy
YES
input
Copy
5 2
0 1 1 1 1
1 1 1 1 1
output
Copy
NO

※ 정답 소스코드 ※

(컴파일 환경: GNU G++11 5.1.0)

#include <iostream> using namespace std; int a[1001]; int b[1001]; int main(void) { int n, m; cin >> n >> m; for(int i = 1; i <= n; i++) { cin >> a[i]; } for(int i = 1; i <= n; i++) { cin >> b[i]; } if(a[1] == 0) { cout << "NO"; return 0; } for(int i = 1; i <= n; i++) { if(a[i] == 1) { if(i == m || (b[i] == 1 && b[m] == 1 && m < i)) { cout << "YES"; return 0; } } } cout << "NO"; return 0; }


728x90
반응형

Comment +0