안경잡이개발자

728x90
반응형

  피보나치 수열 문제와 같은 다이나믹 프로그래밍(Dynamic Programming) 문제를 functoolslru_cache를 이용해 해결할 수 있다. 사용 방법은 간단하다. 점화식을 이용해 재귀 함수를 작성하고, 파이썬의 lru_cache 데코레이터(decorator)를 이용하여 함수가 반환하는 값을 메모이제이션(memoization)할 수 있다. 일반적으로 메모이제이션은 캐싱(caching)과 유사한 의미를 갖는다.

 

  흔히 다이나믹 프로그래밍 문제를 풀 때는 별도의 공간에 함수의 결과를 기록할 필요가 있는데, lru_cache를 사용하면 그럴 필요가 없어지는 것이다.

 

import sys
from functools import lru_cache

sys.setrecursionlimit(int(1e5))

@lru_cache(maxsize=None)
def fibo(n):
    if n < 2:
        return n
    return fibo(n - 1) + fibo(n - 2)


print(fibo(1000))

 

< 실행 결과 >

43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875
728x90
반응형

Comment +0

728x90
반응형

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

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

 

  N개의 수가 있다. 예를 들어 N = 8이라고 하면, 다음과 같이 수가 나열된다.

 

  원래 배열: a1, a2, a3, a4, a5, a6, a7, a8

 

  이때 다음과 같은 규칙에 따라 수를 재나열한다.

 

  변경된 배열: a1, a3, a5, a7, a8, a6, a4, a2

 

  이 문제에서의 요구사항은, 변경된 배열을 보고 원래의 배열을 맞추는 것이다. 문제 해결 아이디어는 굉장히 심플하다. 앞에서부터, 그리고 뒤에서부터 번갈아 가면서 출력하면 된다.

 

for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    
    for i in range(n): 
        if i % 2 == 1:
            print(a[n - (i // 2) - 1], end=' ')
        else:
            print(a[i // 2],end=' ')
    print()

 

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

 

  문장이 주어졌을 때, 하나의 substring을 제거하여 "2020"이라는 문자열을 만들 수 있는지 체크하는 문제다. 이 문제를 풀기 위한 가장 간단한 방법은 제일 앞부분과 제일뒷 부분을 확인하여 "2020"을 만들 수 있는지 확인하는 것이다.

 

(공백) 2020
2 020
20 20
202 0
2020 (공백)

 

for _ in range(int(input())):
    n = int(input())
    data = input()
    
    if data[n - 4:] == "2020":
        print("YES")
    elif data[:1] == "2" and data[n - 3:] == "020":
        print("YES")
    elif data[:2] == "20" and data[n - 2:] == "20":
        print("YES")
    elif data[:3] == "202" and data[n - 1:] == "0":
        print("YES")
    elif data[:4] == "2020":
        print("YES")
    else:
        print("NO")

 

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

 

  하나의 정수 x가 주어졌을 때, 각 자릿수의 합이 x가 되는 정수 중에서 가장 작은 수를 찾는 문제다. 이때 각 자릿수는 서로 달라야 한다. 예를 들어 x = 15일 때는 69가 정답이다. 이 문제의 해결 아이디어는 간단하다. 자릿수의 값을 최대한 크게 설정하면 값이 작아진다는 점을 이용하면 된다. 따라서 9부터 1까지 확인하면서 빼면 된다.

 

  참고로 45 = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9이므로, 45보다 큰 수는 정답이 존재하지 않는다.

 

for _ in range(int(input())):
    x = int(input())
    # 45보다 큰 수는 정답이 없음
    if x >= 46:
        print("-1")
        continue
    result = []
    # 9부터 1까지의 수를 확인하며
    for i in range(9, 0, -1):
        if x >= i:
            result.append(i)
            x -= i
    result.sort()
    print(''.join([str(i) for i in result]))

 

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

 

  N개의 정수가 있다. 그리고 한 번의 연산을 통해 인접한 두 수끼리 합쳐질 수 있다고 한다. 결과적으로 모든 수가 같아지기까지의 최소 연산 횟수를 구하는 문제다. 예를 들어 [1, 2, 2, 1]이 있다고 하자. 이때 [1, 2, 2, 1] → [3, 2, 1] → [3, 3]으로 단 두 번의 연산이면 된다.

 

  이 문제는 알고 보니 정수론(number theory)이었던 문제다. 모든 수의 합을 summary라고 하자. 1부터 N 사이의 값 중에서 summary를 나누어 떨어뜨리는 것이 가능한 수들이 후보군이다. 예를 들어 summary = 12이고, N = 6이라고 해보자. 그러면 남아있는 수의 개수로는 1, 2, 3, 4, 6이 가능하다. 예를 들어 2의 경우에는 [6, 6]을 남기면 되는 것이다.

 

for _ in range(int(input())):
    n = int(input())
    arr = list(map(int, input().split()))
    
    # 후보군(candidate) 찾기
    summary = sum(arr)
    candidates = []
    for i in range(n, 0, -1):
        if summary % i == 0:
            candidates.append(i)
    
    for candidate in candidates:
        target = summary // candidate
        # 모든 수가 target이 되도록 합칠 수 있는지 체크
        check = True
        value = 0
        for x in arr:
            value += x
            if value == target:
                value = 0
            # 합쳤을 때 target보다 크다면, 불가능한 케이스
            elif value > target:
                check = False
                break
        if check:
            print(n - candidate)
            break
728x90
반응형

Comment +0

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
반응형

  일반적으로 경쟁적 프로그래밍(Competitive Programming) 대회, 이른바 알고리즘 대회에서는 종종 애드혹(ad-hoc) 문제가 출제된다. 일반적으로 애드혹 문제라고 하는 것은 해당 문제를 풀기 위해 잘 알려진 정교한(sophisticated) 알고리즘을 적용하지 않고 해결할 수 있는 유형의 문제를 일컫는다. 이러한 유형의 문제는 손으로 직접 해당 문제를 해결하기 위한 (해당 문제만을 위한) 아이디어를 찾아서 문제를 해결할 수 있다. 애드혹 문제들을 굳이 분류하자면 단순히 지시(instruction)를 따르면 되는 구현 유형이나 그리디 유형 알고리즘 혹은 수학 유형으로 분류할 수 있는 경우가 많다.

 

  다시 말해 정형화된 방법론이 아니라, 그 문제를 풀기 위한 창의적인 아이디어를 떠올려야 하는 경우에 애드혹 문제라고 한다.

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
반응형

(이번 대회는 대회 중간에 문제 오류로 인하여 Unrated 판정 공지가 나왔다. 그래서 A번과 B번만 풀었다.)

 

대회 링크: codeforces.com/contests/1418

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

 

  하나의 횃불(Torch)을 만들기 위해서는 1개막대(Stick)1개석탄(Coal)이 필요하다.

 

  우리는 처음에 1개의 막대기를 가지고 시작하며, 두 종류의 연산을 사용할 수 있다.

 

  1번) 1개의 막대기를 x개의 막대기로 교환

  2번) y개의 막대기를 1개의 석탄으로 교환

 

  이때 총 k개의 횃불(Torch)을 만들기 위해 필요한 최소 연산 횟수를 구하면 되는 문제다.

 

[ 문제 해설 ]

 

  우리는 먼저 1개의 막대기에서 시작한다. 따라서 1번 연산을 많이 사용해서 막대기의 개수를 최대한 늘린 뒤에, 그 다음에 2번 연산을 많이 사용해서 석탄을 얻어서 결과적으로 횃불을 만들면 된다.

 

  우리가 막대기를 처음에 증가시킬 때, 연산 1번을 사용할 때마다 막대기를 (x - 1)개씩 증가시킬 수 있다.

 

  k개의 횃불을 만들기 위해서는 k개의 막대기와 k개의 석탄이 필요하다. 이때 k개의 석탄을 만들기 위해서는 y * k개의 막대기가 필요하다. 즉, k개의 횃불을 만들기 위해서(y + 1) * k개의 막대기가 필요한 것이다.

 

  그렇다면 (y + 1) * k개 이상의 막대기를 얻기 위해 1번 연산을 얼마나 사용해야 할까? 바로 다음의 부등식을 만족시키는 한에서 최소한으로 사용해야 할 것이다.

 

  ▶ 필요한 1번 연산의 횟수 * (x - 1) + 1 >= (y + 1) * k

 

  따라서 다음의 코드를 통해서 1번 연산의 횟수의 최솟값을 구할 수 있다.

 

if ((y + 1) * k - 1) % (x - 1) == 0:
    one = ((y + 1) * k - 1) // (x - 1)
else:
    one = ((y + 1) * k - 1) // (x - 1) + 1

 

  이제 2번 연산을 k번 수행하면 최종적으로 k개의 횃불을 만들 수 있다. 따라서 최종적인 코드는 다음과 같다.

 

for _ in range(int(input())):
    x, y, k = map(int, input().split())
    if ((y + 1) * k - 1) % (x - 1) == 0:
        one = ((y + 1) * k - 1) // (x - 1)
    else:
        one = ((y + 1) * k - 1) // (x - 1) + 1
    two = k
    print(one + two)

 

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

 

  N개의 정수를 담고 있는 수열이 있다. N개 중에서 몇 개의 원소는 고정되어(Locked) 위치를 변경할 수 없다. 반면에 고정되어 있지 않은(Unlocked) 원소들은 위치를 서로 변경할 수 있다.

 

  이때 누적 합(Prefix Sum)이 0 미만인 인덱스(index) 중에서 최솟값(Miminum)인 k를 계산해야 한다. 만약 누적합이 0 미만인 인덱스가 없다면 k = 0가 된다.

 

  예를 들어 [-8, 4, -2, -6, 4, 7, 1]이 있다고 해보자. 여기에서 밑줄이 쳐진 원소들은 고정된 원소들이다. 이 경우 [-8, 4, 1, -2, 4, 7, -6]로 수열을 바꾸게 되면, 누적합은 [-8, -4, -3, -5, -1, 6, 0]이다. 이때, 누적합이 0 미만인 인덱스 중에서 최솟값은 k = 5가 된다. (인덱스를 1부터 센다고 했을 때)

 

[ 문제 해설 ]

 

  이 문제는 위치가 고정된 원소를 제외하고, 남은 원소들만 내림차순 정렬을 시켜주면 된다. 그때가 바로 누적 합(Prefix Sum)의 모든 원소가 가장 크게 형성되는 때라고 볼 수 있다.

 

from collections import deque

for _ in range(int(input())):
    n = int(input())
    data = list(map(int, input().split()))
    flag = list(map(int, input().split()))
    
    # 고정되지 않은 원소만 담아서 내림차순 정렬
    temp = []
    for i in range(n):
        if flag[i] == 0:
            temp.append(data[i])
    temp.sort(reverse=True)

    # 최종 결과 리스트 만들기
    result = []
    temp = deque(temp)
    for i in range(n):
        # 고정되지 않은 위치에는 내림차순으로 하나씩 넣기
        if flag[i] == 0:
            result.append(temp.popleft())
        # 고정되어 있다면 그대로 가져오기
        else:
            result.append(data[i])

    # 최종 결과 리스트 출력
    for x in result:
        print(x, end=' ')
    print()
728x90
반응형

Comment +0

728x90
반응형

대회 링크: atcoder.jp/contests/abc178

A번 문제: atcoder.jp/contests/abc178/tasks/abc178_a

 

  이 문제는 입력으로 1이 들어왔을 때 0을 출력하고, 입력으로 0이 들어왔을 때 1을 출력하면 되는 문제다.

 

[ 문제 해설 ]

 

  단순히 하라는 대로 구현하면 된다.

 

[ 정답 코드 ]

 

x = int(input())
 
if x == 0:
    print(1)
else:
    print(0)

 

B번 문제: atcoder.jp/contests/abc178/tasks/abc178_b

 

  a, b, c, d가 입력으로 들어왔을 때 a <= x <= b와 c <= y <= d가 성립하도록 x랑 y를 하나씩 뽑을 수 있다. 이때 만들 수 있는 x * y 중에서 가장 큰 값이 무엇인지 구하면 되는 문제다.

 

  단, a, b, c, d는 -10억부터 +10억 사이의 정수다.

 

[ 문제 해설 ]

 

  다음의 4가지 경우 중에서 가장 큰 값을 출력하면 된다.

 

  1) a * c

  2) a * d

  3) b * c

  4) b * d

 

[ 정답 코드 ]

 

a, b, c, d = map(int, input().split())
 
print(max(a * c, a * d, b * c, b * d))

 

C번 문제: atcoder.jp/contests/abc178/tasks/abc178_c

 

  길이가 n인 수열 {A1, A2, A3, ..., An}이 있을 때, 다음의 조건을 만족하는 수열의 개수를 세면 되는 문제다.

 

  ▶ 0 <= Ai <= 9

   값이 0인 원소가 하나 이상 존재한다.

   값이 9인 원소가 하나 이상 존재한다.

 

[ 문제 해설 ]

 

  이 문제는 N이 최대 1,000,000일 수 있으므로 O(N) 안쪽으로 해결해야 한다. 따라서 전형적인 DP를 이용해 문제를 해결할 수 있다.

 

  DP[n][0]: 길이가 N이면서 조건을 만족하는 수열의 개수 (단, 0의 개수: 0, 9의 개수: 0)

  DP[n][1]: 길이가 N이면서 조건을 만족하는 수열의 개수 (단, 0의 개수: 1 이상, 9의 개수: 0)

  DP[n][2]: 길이가 N이면서 조건을 만족하는 수열의 개수 (단, 0의 개수: 0, 9의 개수: 1 이상)

  DP[n][3]: 길이가 N이면서 조건을 만족하는 수열의 개수 (단, 0의 개수: 1 이상, 9의 개수: 1 이상)

 

  위와 같이 정의하여 해결할 수 있다.

 

  ... 그냥 더 쉽게 수학 공식으로 해결하자.

 

  ▶ 모든 경우의 수: 10^n

  ▶ 9를 제외한 경우의 수: 9^n

  ▶ 0을 제외한 경우의 수: 9^n

  ▶ 0과 9 둘 다 없을 때의 경우의 수: 8^n

 

  따라서 전체 경우의 수는 10^n - 9^n - 9^n + 8^n이다. 이를 포함배제의 원리(Principle of inclusion-exclusion)라고도 한다.

 

[ 정답 코드 ]

 

  참고로 값이 매우 매우 커질 수 있으나 파이썬(Python)의 경우 이를 효과적으로 처리한다.

 

n = int(input())
mod = int(1e9) + 7

result = ((10 ** n) - 2 * (9 ** n) + (8 ** n)) % mod
print(result)

 

D번 문제: atcoder.jp/contests/abc178/tasks/abc178_d

 

  하나의 자연수 S가 있을 때, 다음의 조건을 만족하는 수열의 개수를 구하고자 한다.

 

  ▶ 모든 원소가 3 이상의 정수

  ▶ 모든 원소의 합이 S

 

  예를 들어 S = 7이라고 하면 {7], {3, 4}, {4, 3}이 있으므로 답은 3이다.

 

[ 문제 해설 ]

 

  이 문제는 S가 최대 2,000이므로 이차 시간 안에 동작하는 알고리즘을 고안해야 한다. 또한 최적 부분 구조(Optimal Substructure)가 성립하므로 DP를 이용해 문제를 해결할 수 있다. 예를 들어 S = 7의 모든 경우의 수는 다음의 모든 경우를 고려한 것과같다.

 

  ▶ {7}

  ▶ {3}에 DP[4]의 모든 수열을 이어 붙인 것들

  ▶ {4}에 DP[3]의 모든 수열을 이어 붙인 것들

  ▶ {5}에 DP[2]의 모든 수열을 이어 붙인 것들

  ▶ {6}에 DP[1]의 모든 수열을 이어 붙인 것들

 

  이런 아이디어를 고려하면 다음과 같은 코드로 문제를 해결할 수 있다.

 

[ 정답 코드 ]

 

s = int(input())
d = [0] * 2001

# 일단 기본적인 초기 값들 계산해보기
d[0] = 0
d[1] = 0
d[2] = 0
d[3] = 1 # {3}
d[4] = 1 # {4}
d[5] = 1 # {5}
d[6] = 2 # {6}, {3, 3}
d[7] = 3 # {6}, {3, 4}, {4, 3}
d[8] = 4 # {8}, {3, 5}, {4, 4}, {5, 3}
d[9] = 6 # {9}, {3, 6}, {4, 5}, {5, 4}, {6, 3}, {3, 3, 3}
 
for i in range(10, 2001):
    summary = 1 # 일단 자기 자신 하나를 원소로 삼는 경우
    for j in range(3, i):
        summary += d[i - j]
        summary = summary % (int(1e9) + 7)
    d[i] = summary
 
print(d[s])

 

E번 문제: atcoder.jp/contests/abc178/tasks/abc178_e

 

  2D 공간에 N개의 점(Point)이 존재한다. 이때 맨해튼 거리(Manhattan Distance)가장 먼 두 개의 점을 찾는 문제다. 예를 들어 i와 j 두 점이 있으면 맨해튼 거리는 |Xi - Xj| + |Yi - Yj|를 의미한다.

 

[ 문제 해설 ]

 

  먼저 Xi <= Xj라고 했을 때 다음의 두 경우로 나눌 수 있다.

 

  ▶ 만약 Yi <= Yj라면 거리는 (Xj + Yj) - (Xi + Yi)이다.

  ▶ 만약 Yi > Yj라면 거리는 (Xj - Yj) - (Xi - Yi)이다.

 

  이 문제는 잘 알려진 문제로, 맨해튼 거리이기 때문에 이러한 조건이 성립한다. 참고로 맨해튼 거리가 아니라 유클리드 거리라면 컨벡스 헐(Convex Hull)을 활용해야 제한 시간 안에 문제를 해결할 수 있다.

 

  첫 번째 경우를 보면 X + Y만 구하면 된다는 것을 알 수 있다.

  두 번째 경우를 보면 X - Y만 구하면 된다는 것을 알 수 있다.

 

  결과적으로 max(max(x + y) - min(x + y), max(x - y) - min(x - y))를 출력하면 된다.

 

[ 정답 코드 ]

 

n = int(input())
plus = []
minus = []
 
for i in range(n):
    x, y = map(int, input().split())
    plus.append(x + y)
    minus.append(x - y)
 
result = max(max(plus) - min(plus), max(minus) - min(minus))
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