안경잡이개발자

728x90
반응형

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

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

 

[ 문제 해설 ]

 

  이 문제는 그림을 그려가면서 다양한 케이스들을 확인해 보면, 문제 풀이 아이디어를 빠르게 떠올릴 수 있다.

 

  행이나 열의 크기가 1이라면, 항상 퍼즐을 풀 수 있다. 그리고 행이나 열의 크기가 둘 다 2, 2일 때에도 항상 퍼즐을 풀 수 있다. 하지만 그 이외의 모든 경우에 대해서는 퍼즐을 풀 수 없다.

 

[ 정답 코드 ]

 

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

    # 행이나 열의 크기가 1이라면 풀 수 있음
    if n == 1 or m == 1:
        print("YES")
    # 행과 열의 크기가 모두 2일 때 풀 수 있음
    elif n == 2 and m == 2:
        print("YES")
    # 이외의 경우에는 모두 풀 수 없음
    else:
        print("NO")

 

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


  이 문제는 N장의 카드를 가지고 있을 때, 최대한 높은 층의 카드 쌓기를 반복적으로 수행하는 문제이다. 그래서 마지막에 몇 개의 카드 피라미드가 존재할 지 출력하면 된다.

 

  아래의 그림에서 볼 수 있듯이,

 

  1층짜리 피라미드: 2장 필요

  2층짜리 피라미드: 7장 필요

  3층짜리 피라미드: 15장 필요

 

 

  그래서, 예를 들어 N = 24라고 해보자.

 

  처음에 15장을 투자해 3층짜리 피라미드를 짓고, 9장이 남는다.

  그리고 7장을 투자해 2층짜리 피라미드를 짓고, 2장이 남는다.

  남은 2장을 투자해 1층짜리 피라미드를 짓고, 0장이 남는다.

 

  그래서 결과적으로 피라미드를 3개 지을 수 있게 된다.

 

[ 문제 해설 ]

 

  이 문제를 해결하기 위한 방법은 간단하다. 문제에서 요구하는 내용을 그대로 구현하면 된다. 이 때 피라미드는 층이 증가할수록 다음과 같이 카드가 필요하다는 특징이 있다.

 

  - 1층 피라미드: 2장

  - 2층 피라미드: 2장 + 5장

  - 3층 피라미드: 2장 + 5장 + 8장

  - 4층 피라미드: 2장 + 5장 + 8장 + 11장

  - 5층 피라미드: 2장 + 5장 + 8장 + 11장 + 14장

 

  즉, 층이 올라갈수록 '추가적으로 필요한 카드의 개수는 3장씩 증가'한다.

 

[ 정답 코드 ]

 

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

    # 남아있는 카드가 2장 이상이라면, 피라미드 만들기 수행
    while n >= 2:
        # 초기 상태
        summary = 0
        count = 2
        height = 0

        # 더 높이 쌓을 수 없을 때까지 쌓기
        while n >= summary + count:
           summary += count
           count += 3
           height += 1

        # 피라미드 하나를 완성했으므로, n에서 필요한 카드의 개수만큼 빼주기
        result += 1
        n -= summary

    print(result)

 

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


  이 문제는 비둘지깁의 원리같은 느낌의 문제다. 

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

대회 링크: http://codeforces.com/contest/1341

A번 문제: http://codeforces.com/contest/1341/problem/A

 

  이 문제는 n개의 쌀알의 무게의 범위가 각각 [a - b, a + b]일 때, 이 쌀알들의 무게를 모두 더한 것이 [c - d, c + d]에 들어갈 수 있는지 물어보고 있다.

 

  입력으로는 매 테스트 케이스마다 n, a, b, c, d가 입력된다.

 

  예를 들어 7 20 3 101 18이 들어오게 되면, 각 쌀알의 무게는 [17, 23] 범위 중 하나가 된다. 이 때, 모든 쌀알의 무게를 더한 것이 [83, 119] 범위 중 하나가 될 수 있어야 한다는 것이다. 이 경우, 각 쌀알의 무게가 17이라고 하면, 모든 쌀알의 무게를 더한 것은 119가 되므로 조건을 만족한다. 따라서 "Yes"를 출력하게 된다.

 

[ 문제 해설 ]

 

  이 문제는 단순히 [(a - b) * n, (a + b) * n]이 [c - d, c + d]과 교차하는지(Intersecting) 확인하면 된다.

 

  따라서, 일직선 상의 두 직선이 교차하는 지 확인하는 알고리즘을 사용하면 된다.

 

  만약에 (line_1.left <= left_2.right and line_1.right >= line_2.left)이 성립한다면, 교차한다고 볼 수 있다.

 

[ 정답 코드 ]

 

for _ in range(int(input())):
    n, a, b, c, d = map(int, input().split())
    # 일직선상의 두 직선이 교차하는지 검사
    if (a - b) * n <= c + d and (a + b) * n >= c - d:
        print("Yes")
    else:
        print("No")

 

B번 문제: http://codeforces.com/contest/1341/problem/B

 

  산에는 고점(Peek)들이 존재하는데, 뾰족하게 올라온 부분이라고 보면 된다. 이 때, 제일 왼쪽과 제일 오른쪽은 제외한다.

 

  예를 들어 산 데이터가 [3, 1, 4, 1, 5, 9, 2, 6]이라고 하면, 3의 위치와 6의 위치에 고점(Peeks)들이 있는 것이다.

 

  문제에서는 K만큼을 차지하는 길이의 문을 산에 던진다. 산으로 던진 문은 고점에 닿은 위치에서 쪼개진다고 한다. 이 문제에서는 문이 최대한 많은 개수로 쪼개지길 원한다.

 

  예를 들어 산 데이터가 [3, 2, 3, 2, 1]이고, 문의 길이가 3이라면,

 

  i) 1번째 위치에 놓았을 때: [3, 2, 3, 2, 1] → 쪼개진 문의 개수는 1개

  ii) 2번째 위치에 놓았을 때: [3, 2, 3, 2, 1] 쪼개진 문의 개수는 2개

  iii) 3번째 위치에 놓았을 때: [3, 2, 3, 2, 1] 쪼개진 문의 개수는 1개

 

  위와 같이 쪼개진 문의 개수가 나열된다. ii)의 경우에는 3의 위치에 있는 고점(Peek)이 문을 정확히 반으로 가르기 때문에 쪼개진 문의 개수가 2개가 되는 것이다. i)와 iii)의 경우에는 문이 쪼개지지 않는다.

 

[ 문제 해설 ]

 

  일단, 길이가 K인 모든 구간을 계산한다고 해보자. 그렇다면, 다음의 공식이 성립한다.

 

  쪼개지는 문의 개수 = 그 구간에 포함된 고점 개수 - 구간의 시작이 고점인지의 여부 - 구간의 끝이 고점인지의 여부

 

  이 문제는 투 포인터(Two Pointers) 알고리즘으로 해결할 수 있다. 투 포인터 알고리즘은 특정 구간안에서의 어떠한 계산을 선형 시간에 해결하기 위해 효과적으로 사용할 수 있다. (정확히 구간이 K칸을 차지할 때만 계산하지 않고, K이하면 계산하도록 하였다. 어차피 이렇게 해도 최적의 해가 나온다.)

 

[ 정답 코드 ]

 

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

    # 모든 고점(Peak) 정보를 입력 받기
    peaks = set()
    for i in range(1, n - 1):
      if data[i - 1] < data[i] and data[i] > data[i + 1]:
        peaks.add(i)
 
    ''' 투 포인터(Two Pointers) 알고리즘 수행 '''
    end = 0 # 구간의 끝 인덱스
    peak_count = 0 # 구간에 존재하는 고점(Peak)의 개수
    result = 0
    index = 0
  
    for start in range(n): # 구간의 시작 인덱스를 증가시키며
      while end < n and end - start < k:
        # 끝 구간이 고점(Peak)이라면 고점의 개수 증가
        if end in peaks:
          peak_count += 1
        
        # 구간의 시작 혹은 끝이 고점이라면 1씩 빼기
        additional = 0
        if start in peaks:
          additional -= 1
        if end in peaks:
          additional -= 1
        
        # 가장 많이 쪼개지는 경우를 저장
        if result < peak_count + additional:
          result = peak_count + additional
          index = start
  
        # 시작 구간이 고점(Peak)이라면 고점의 개수 증가
        if start in peaks:
          peak_count -= 1
      
        end += 1
    
    print(result + 1, index + 1)

 

C번 문제: http://codeforces.com/contest/1341/problem/C

 

  이 문제는 설명이 길어서 문제 설명은 생략한다.

 

[ 문제 해설 ]

 

  기본적으로 문제에서는 1부터 n까지의 수를 차례대로 놓아서 순열을 만든다고 한다.

 

  이 문제는 문제 해결의 아이디어만 떠올릴 수 있으면 바로 해결할 수 있다. 

 

  문제 해결의 아이디어는 바로 특정한 위치에 i번째 수를 놓게 되면, 오른쪽 끝에 도달할 때까지 1씩 증가시키며 그 다음수를 놓아야 한다는 사실이다. 예를 들어 n = 5일 때, 1을 3번째 자리에 놓게 되면, 무조건 2는 4번째 자리에 두고, 3은 5번째 자리에 두어야 한다.

 

  한 번 순열 [2, 3, 4, 5, 1]을 생각해보자. 이것은 만들 수 있는 순열이다. 1을 5번째 자리에 두고, 2를 1번째 자리에 두면 자연스럽게 [2, 3, 4, 5, 1]가 형성된다. 따라서 "Yes"를 출력하면 된다.

 

  반면에 순열 [1, 3, 2]를 생각해보자. 이것은 만들 수 없는 순열이다. 1을 1번째 자리에 두면, 무조건 [1, 2, 3]만을 만들게 된다. 따라서 "No"를 출력하면 된다.

 

[ 정답 코드 ]

 

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

    # 각 수별로 몇 번째 자리에서 등장하는지 기록
    my_map = [0] * (n + 1)
    for i in range(n):
        my_map[data[i]] = i + 1
    
    # n + 1의 위치를 '끝'으로 기록 (왼쪽에서 오면, 여기에서 멈추도록)
    blocked = set()
    blocked.add(n + 1)
 
    now = 1
    result = True
 
    # 수를 1부터 차례대로 확인하며
    while now < n:
        # 해당 수가 등장한 위치를 가져오기
        index = my_map[now]
        # 해당 수의 위치를 '끝'으로 기록 (왼쪽에서 오면, 여기에서 멈추도록)
        blocked.add(index)
        # 더 이상 오른쪽으로 갈 수 없을 때까지 1씩 증가시키며 이동
        if index + 1 not in blocked:
            # 만약, 오른쪽에 있는 수가 자기보다 1만큼 큰 수가 아니라면
            if my_map[now + 1] != index + 1:
                result = False
                break
        now += 1
  
    if result:
        print("Yes")
    else:
        print("No")

 

728x90
반응형

Comment +0

728x90
반응형

대회 링크: http://codeforces.com/contest/1335

A번 문제: http://codeforces.com/contest/1335/problem/A

 

  n개의 사탕을 두 사람이 나눠야 한다. 두 사람이 가지는 사탕의 수를 각각 a와 b라고 하자. 이 때 a > 0, b > 0, a > b가 되도록 하는 경우의 수를 출력하는 문제다.

 

[ 문제 해설 ]

 

  예를 들어, 다음과 같은 n들을 고려해보자.

 

  n = 1일 때는 조건에 맞게 나눌 수 있는 경우가 없다.

  n = 2일 때는 조건에 맞게 나눌 수 있는 경우가 없다.

  n = 3일 때는 (2, 1)로 나눌 수 있으므로 경우의 수는 1이다.

  n = 4일 때는 (3, 1)로 나눌 수 있으므로 경우의 수는 1이다.

  n = 5일 때는 (3, 2), (4, 1)로 나눌 수 있으므로 경우의 수는 2다.

  n = 6일 때는 (4, 2), (5, 1)로 나눌 수 있으므로 경우의 수는 2다.

  n = 7일 때는 (4, 3), (5, 2), (6, 1)로 나눌 수 있으므로 경우의 수는 3이다.

 

  결과적으로 경우의 수는 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, ... 순으로 나열되는 것을 알 수 있다. 따라서 단순히 (n - 1)를 2로 나눈 몫을 출력하면 그것이 정답이다.

 

[ 정답 코드 ]

 

for _ in range(int(input())):
    n = int(input())
    print((n - 1) // 2)

 

B번 문제: http://codeforces.com/contest/1335/problem/B

 

  길이가 n인 문자열 s를 만드는데, 길이가 a인 모든 부분 문자열들이 b개의 서로 다른 문자들로 구성되도록 하는 문제다. 조건만 만족한다면 길이가 n인 문자열 s를 아무거나 출력해도 된다.

 

  예를 들어 n = 7, a = 5, b = 3일 때를 고려해보자. 이 때는 tleelte가 정답이 될 수 있다.

 

[ 문제 해설 ]

 

  이 문제는 길이가 a인 부분 문자열 k를 만들어서 순환적으로 출력하면 된다. n = 7, a = 5, b = 3일 때를 생각해보자.

 

  k = ['a', 'b', 'c', 'a', 'a']로 만들게 되면, 예를 순환적으로 출력하면 다음과 같다.

 

  {'a', 'b', 'c', 'a', 'a', 'a', 'b', 'c', 'a', 'a', 'a', 'b', 'c', 'a', 'a', ...}

 

  이렇게 되면, 길이가 5인 어떤 부분 문자열도 3개의 서로 다른 문자로 구성된다. 즉, 문제 해결의 아이디어는 앞에서부터 b만큼은 'a'부터 시작해 차례대로 문자를 담고, 나머지는 그냥 'a'만 나열하도록 문자열 k를 만든다. 이후에 k를 순환적으로 출력하면 정답이다.

 

[ 정답 코드 ]

 

for _ in range(int(input())):
    n, a, b = map(int, input().split())
    k = []
    
    # 앞의 b만큼은 'a'부터 시작해 차례대로 문자를 담기
    for i in range(b):
        k.append(chr(ord('a') + i))
    # 나머지는 그냥 'a'만 나열하도록 문자를 담기
    for i in range(a - b):
        k.append('a')
  
    # 이제 문자열 k를 순환적으로 출력하면 정답
    for i in range(n):
        print(k[i % a], end='')
    print()

 

C번 문제: http://codeforces.com/contest/1335/problem/C

 

  n명의 학생을 두 팀으로 나눌 때, 첫 번째 팀은 모두 스킬이 다르고 두 번째 팀은 모두 스킬이 같도록 구성하고자 한다. 단, 두 팀의 인원이 동일해야 한다. 이 때 팀의 가능한 최대 인원 수를 찾는 문제다.

 

  예를 들어 n = 7이고, 학생들의 스킬이 {4, 2, 4, 1, 4, 3, 4}라면 다음과 같이 나누었을 때 각 팀의 인원수가 제일 많다.

 

  첫 번째 팀: {1, 2, 3}

  두 번째 팀: {4, 4, 4}

 

  이 때 팀의 인원수는 3이다.

 

[ 문제 해설 ]

 

  이 문제는 각 스킬의 번호마다 등장 횟수를 체크(count_map)하고, 스킬의 번호가 총 몇 개 있는지 체크(distinct_count)하여 해결할 수 있다.

 

  예를 들어 위의 예시에서는 각 스킬의 번호마다 등장 횟수가 다음과 같다.

 

  1번 스킬: 1명

  2번 스킬: 1명

  3번 스킬: 1명

  4번 스킬: 3명

 

  또한 전체 스킬의 번호가 총 4개가 된다.

 

  이제 각 스킬 번호에 대해서, 그 스킬을 가진 학생들만을 오른쪽 팀에 두는 경우들을 고려하면 된다. 다만, 한 명의 학생은 왼쪽 팀에 넘겨 주어도 괜찮다. 이를 이용해 정답 코드를 작성할 수 있다.

 

[ 정답 코드 ]

 

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

    count_map = {}
    distinct_count = 0
    for i in data:
        if i not in count_map:
            count_map[i] = 1
            distinct_count += 1
        else:
            count_map[i] += 1
  
    # 각 스킬 번호를 확인하며
    for (key, value) in count_map.items():
        # 해당 스킬을 가진 학생을 두 번째 팀에 두는 경우를 고려하여, 최대 인원 수 찾기
        now = max(min(count_map[key], distinct_count - 1), min(count_map[key] - 1, distinct_count))
        result = max(result, now)
    print(result)

 

D번 문제: http://codeforces.com/contest/1335/problem/D

 

  이 문제는 전형적인 스도쿠 퍼즐이 무엇인지 알아야 한다. 다음과 같이 이미 완성된 스도쿠 보드가 있다고 해보자.

 

 

  이 때 안티 스도쿠란, 다음의 조건을 만족하는 보드를 말한다.

 

  1) 각 행에 대하여 최소한 두 개의 원소가 같아야 한다.

  2) 각 열에 대하여 최소한 두 개의 원소가 같아야 한다.

  3) 모든 3 x 3 블럭(Block)에서 최소한 두 개의 원소가 같아야 한다.

 

  이번 문제는 완성된 스도쿠 보드가 입력되었을 때, 안티 스도쿠를 만들어 출력하는 문제다.

 

[ 문제 해설 ]

 

  깊게 고민하면 문제 해결 아이디어를 떠올릴 수 있다. 다양한 방법이 있을 수 있겠지만, 저자는 다음과 같이 풀었다. 바로 다음의 9가지 위치에 있는 원소들의 값을 기존의 값이 아닌 다른 아무 값으로나 바꾸면 된다.

 

 

  따라서 9개의 칸에 있는 각 원소의 값이 1인 경우에는 2로 바꾸고, 1이 아닌 경우에는 1로 바꾸면 된다.

 

[ 정답 코드 ]

 

for _ in range(int(input())):
    data = []
    for i in range(9):
        data.append(list(map(int, input())))

    # 9가지 위치의 값을 기존의 값이 아닌 다른 값으로 변경
    data[0][0] = 2 if data[0][0] == 1 else 1
    data[1][3] = 2 if data[1][3] == 1 else 1
    data[2][6] = 2 if data[2][6] == 1 else 1
    data[3][1] = 2 if data[3][1] == 1 else 1
    data[4][4] = 2 if data[4][4] == 1 else 1
    data[5][7] = 2 if data[5][7] == 1 else 1
    data[6][2] = 2 if data[6][2] == 1 else 1
    data[7][5] = 2 if data[7][5] == 1 else 1
    data[8][8] = 2 if data[8][8] == 1 else 1
  
    for i in range(9):
        print(''.join(map(str, data[i])))
728x90
반응형

Comment +0

728x90
반응형

대회 링크: http://codeforces.com/contest/1343

A번 문제: http://codeforces.com/contest/1343/problem/A

 

  정수 n이 주어졌을 때, 정수 k가 1보다 큰 조건 하에서 다음을 만족시키는 양수 x가 하나라도 있는지 찾는 문제다.

 

 

[ 문제 해설 ]

 

  이 문제는 완전 탐색(Brute Forcing)으로 해결할 수 있다. k를 2부터 쭉 증가시켜보자. n은 다음과 같이 표현된다.

 

  3x = n

  7x = n

  15x = n

  31x = n

  63x = n

  ...

 

  보면 x의 계수가 기하급수적으로 증가한다. 이 때 n은 최대 1,000,000,000이기 때문에, 모든 경우의 수를 고려해도 빠르게 문제를 풀 수 있다. (대략 k가 30만 되어도 계수는 10억에 근접할 것이다.)

 

  그래서 3x, 7x, 15x, 31x, 63x, ... 이렇게 증가 시키면서, n이 각 계수로 나누어 떨어지는지 확인한다. 만약 나누어 떨어진다면 그 때의 x를 출력하면 정답이다.

 

[ 정답 코드 ]

 

for _ in range(int(input())):
    n = int(input())
    coefficient = 2
    now = 3 # now는 3, 7, 15, 31, ...와 같이 증가한다.
    while True:
        # n이 now로 나누어 떨어진다면
        if n % now == 0:
            # 그 몫을 출력한다.
            print(n // now)
            break
        coefficient *= 2
        now += coefficient

 

B번 문제: http://codeforces.com/contest/1343/problem/B

 

  배열의 크기 n이 주어졌을 때, 이 배열의 앞 부분 절반은 짝수 원소로만 구성되고, 뒷 부분 절반은 홀수 원소로만 구성된다고 한다. 이 때 모든 원소들은 서로 다르다. 앞 부분의 합과 뒷 부분의 합이 동일하게 되는 리스트를 하나라도 찾으면 되는 문제다.

 

  예를 들어 N = 4일 때, 2 4 1 5를 찾으면 정답이다. N = 8일 때는 2 4 6 8 1 3 5 11를 찾으면 정답이다.

 

[ 문제 해설 ]

 

  이 문제는 홀수 합의 특징을 생각하면 어렵지 않게 풀 수 있다. 홀수를 홀수 번 더하면 홀수이다. 즉, N / 2가 홀수라면 리스트를 만들 수 없다. 예를 들어 N = 6 이라면, 리스트를 만들 수 없다. 즉 N이 4의 배수일 때만 리스트를 만들 수 있다. 그렇다면 N이 4의 배수일 때는 리스트를 어떻게 만들면 될까?

 

  앞 부분 절반은 그냥 2부터 하나씩 나열한다. 뒷 부분 절반은 앞 부분에서 1씩 더하거나 빼서 만들 수 있다. (정확히는 뒷 부분 절반의 합이 앞 부분 절반의 합이 되어야 하므로, 뒷 부분 절반을 또 절반으로 나누어서 처리하면 된다.)

 

[ 정답 코드 ]

 

for _ in range(int(input())):
    n = int(input())
    # N이 4의 배수일 때 리스트를 만들 수 있다.
    if n % 4 != 0:
        print("NO")
    else:
        print("YES")
        front = []
        # 앞 부분 절반(짝수 부분)은 2부터 하나씩 출력
        for i in range(1, n // 2 + 1):
            print(i * 2, end=' ')
            front.append(i * 2)
        # 뒷 부분 절반(홀수 부분)의 절반은 -1씩 해서 출력
        for i in range(n // 4):
            print(front[i] - 1, end=' ')
        # 뒷 부분 절반(홀수 부분)의 남은 절반은 +1씩 해서 출력
        for i in range(n // 4, n // 2):
            print(front[i] + 1, end=' ')
        print()

 

C번 문제: http://codeforces.com/contest/1343/problem/C

 

  리스트가 주어졌을 때, 리스트의 원소를 앞에서부터 하나씩 확인하며 원소를 고른다. 단, 양수와 음수를 번갈아 가면서 원소를 하나씩 골라야 한다. 처음에 양수를 골랐으면, 다음 번에는 음수를 골라야 한다. 반대로 처음에 음수를 골랐으면, 다음 번에는 양수를 골라야 한다.

 

  이 때, 원소들을 골라서 만들어지는 가장 긴 부분수열 중에서 원소의 합이 가장 큰 것을 찾는 것이 요구사항이다.

 

  예를 들어 수열이 [-2, 8, 3, 8, -4, -15, 5, -2, -3, 1]이라면, 정답 부분수열은 [-2, 8, -4, 5, -2, 1]이 된다. 이 부분 수열의 합은 6이다.

 

[ 문제 해설 ]

 

  이 문제는 같은 부호를 가지는 데이터들을 묶어서 해결할 수 있다. 예를 들어 [-2, 8, 3, 8, -4, -15, 5, -2, -3, 1]라는 수열이 있다면, 이를 다음과 같이 인접한 원소끼리 묶도록 한다.

 

  [-2, 8, 3, 8, -4, -15, 5, -2, -3, 1]

 

  이 때, 같은 묶음 중에서 가장 큰 수를 각각 뽑으면 된다. 이 때 합은 6이 된다.

 

  [-28-45-21]

 

  이를 코드로 옮기면 정답이다.

 

[ 정답 코드 ]

 

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

    # 시작점이 양수인지 음수인지 기록(양수: 1, 음수: -1)
    if data[0] > 0:
        sign = 1
    else:
        sign = -1
  
    # 같은 부호들을 담을 리스트
    array = []
 
    # 리스트의 원소를 하나씩 확인하며
    for x in data:
        # 현재 양수일 때 양수가 나온 경우
        if sign == 1 and x > 0:
            # 같은 부호이므로 담기
            array.append(x)
        # 현재 양수일 때 음수가 나온 경우
        if sign == 1 and x < 0:
            # 현재 부호를 음수로 변환
            sign = -1
            result += max(array)
            array = [x]
        # 현재 음수일 때 음수가 나온 경우
        if sign == -1 and x < 0:
            # 같은 부호이므로 담기
            array.append(x)
        # 현재 음수일 때 양수가 나온 경우
        if sign == -1 and x > 0:
            # 현재 부호를 양수로 변환
            sign = 1
            result += max(array)
            array = [x]
  
    result += max(array)
    print(result)

 

D번 문제: http://codeforces.com/contest/1343/problem/D

 

  길이가 n인 수열이 주어진다. (n은 짝수) 이 수열의 모든 원소는 k 이하의 값을 가진다.

 

  이 때 대칭되는 원소들의 합을 모두 x로 만들고자 한다. 이를 위해 원소를 하나씩 골라서 그 원소의 값을 k 이하의 수로 바꾸는 연산을 수행할 수 있다. 결과적으로 최소 연산의 횟수를 출력하면 되는 문제이다.

 

  예를 들어 [1, 2, 1, 2]의 경우 대칭되는 원소의 합이 각각 3, 3이다. 따라서 x = 3으로 설정했을 때, 연산이 필요하지 않다. 따라서 최소 연산 횟수는 0이다.

 

  또한 [12, 2, 1]의 경우 대칭되는 원소의 합이 각각 4, 2이다. 따라서 x = 4으로 설정했을 때, 첫 번째 원소를 3으로 변경하면 된다. 최소 연산 횟수는 1이다.

 

  또한 [6, 1, 1, 7, 6, 3, 4, 6]의 경우 대칭되는 원소의 합이 각각 13, 4, 5, 12이다. 따라서 x = 8로 설정했을 때, 최소 연산 횟수로 4가 나올 수 있다.

 

[ 문제 해설 ]

 

  이 문제는 아이디어만 잘 떠올리면 쉽게 해결할 수 있는 문제다. 일단 각 대칭 쌍마다 하나의 원소를 변경할 수 있다고 가정해보자. 예를 들어 3번째 예제를 가지고 생각해보자.

 

  [6, 1, 1, 7, 6, 3, 4, 6]를 확인하면, 각 대칭 쌍을 정렬하여 나열하면 다음과 같다. 총 네 개의 쌍이 존재한다.

 

  (1, 3): 합 = 4

  (1, 4): 합 = 5

  (6, 6): 합 = 12

  (6, 7): 합 = 13

 

  이 때 각 대칭 쌍의 원소 중 하나의 값을 변경할 수 있을 때의 범위는 다음과 같다.

 

  (1, 3) → [2, 10]

  (1, 4) → [2, 11]

  (6, 6) → [7, 13]

  (6, 7) → [7, 14]

 

  결과적으로 모든 쌍들의 [lower_bound, upper_bound] 범위를 고려해보자. x를 2부터 2 * n까지 증가시키면서 확인한다고 생각해보자. x = 2라고 하면 (1, 3)과 (1, 4)의 범위에 포함되어 있으므로, 이들은 원소를 1개씩만 바꾸면 된다. 나머지 두 쌍은 원소를 2개 모두 바꾸어야 한다. 즉, x = 2일 때 최소 연산 횟수는 6이 될 것이다. 만약에 x = 7이라면 어떨까? 모든 대칭 쌍이 원소를 1개씩만 바꾸면 된다. 이 때 최소 연산 횟수는 4가 된다. 따라서 x를 증가 시키면서 매 x에 대하여 lower_bound와 upper_bound를 고려해주면 된다.

 

  사실 [2, 2 * n] 범위에 대해서 x를 모두 고려할 필요는 없다. 각 대칭 쌍에 대하여 ① 대칭 쌍의 합, ② lower_bound, upper_bound 세 가지에 대해서만 고려하면 된다. 이들을 포인트(points)라고 하겠다. 포인트는 오름차순 정렬이 되어 있어야 한다.

 

  결과적으로 포인트를 하나씩 확인할 것이다. 이를 위해 lower_bound의 개수를 in_map에 기록하고, upper_bound의 개수를 out_map에 기록한다. 또한 대칭 쌍의 합은 sum_map에 기록하도록 하자. 이제 최소 연산 횟수를 구할 수 있다.

 

points 2 4 5 7 10 11 12 13 14
in_map 2     2          
out_map         1 1   1 1
sum_map   1 1       1 1  
연산 횟수 6 5 5 4 4 5 5 5 7

 

  결과적으로 최소 연산 횟수는 4가 되는 것이다.

 

[ 정답 코드 ]

 

for _ in range(int(input())):
    n, k = map(int, input().split())
    data = list(map(int, input().split()))
  
    # 3개의 해시 맵(Hash Map)을 사용합니다.
    in_map = {}
    out_map = {}
    sum_map = {}

    # x의 값으로 확인해야 할 포인트들
    points = set()
 
    for i in range(n // 2):
        min_value = min(data[i], data[n - i - 1])
        max_value = max(data[i], data[n - i - 1])

        # lower_bound, upper_bound, 대칭 쌍의 합 계산
        lower_bound = min_value + 1
        upper_bound = max_value + k
        sum_value = min_value + max_value

        # 모든 lower_bound를 in_map에 기록합니다.
        if lower_bound in in_map:
            in_map[lower_bound] += 1
        else:
            in_map[lower_bound] = 1

        # 모든 upper_bound를 out_map에 기록합니다.
        if upper_bound in out_map:
            out_map[upper_bound] += 1
        else:
            out_map[upper_bound] = 1

        # 모든 대칭 쌍의 합을 sum_map 기록합니다.
        if sum_value in sum_map:
            sum_map[sum_value] += 1
        else:
            sum_map[sum_value] = 1

        points.add(lower_bound)
        points.add(upper_bound)
        points.add(sum_value)
  
    points = sorted(points)
 
    now_sum = 0
    result = n
  
    for i in points:
        # lower_bound의 개수만큼 더하기
        in_count = 0
        if i in in_map:
            in_count = in_map[i]
        now_sum += in_count

        # sum의 개수 구하기
        sum_count = 0
        if i in sum_map:
            sum_count = sum_map[i]

        # 최소 연산 횟수 계산
        now_total = n - (now_sum + sum_count)
        result = min(result, now_total)

        # upper_bound의 개수만큼 빼기
        out_count = 0
        if i in out_map:
            out_count = out_map[i]
        now_sum -= out_count
    
    print(result)
728x90
반응형

Comment +0

728x90
반응형

  이번 시간에는 알고리즘 대회를 위한 C++ 대회 환경구성해보도록 하겠습니다. 가장 먼저, 자신의 디버깅 및 개발을 위한 개발환경을 구축하셔야 합니다. 저는 정말정말 가벼운 개발환경인 Dev C++을 선호하는 편입니다. 따라서 Dev C++을 기준으로 설명드리고자 합니다.


  Dev C++ 설치 경로: https://sourceforge.net/projects/orwelldevcpp/


  Dev C++을 설치하셨으면, 실행 이후에 C++11로 컴파일 옵션 설정을 해주시면 됩니다. C++11에는 알고리즘 대회에 적용하기 쉬운 다양한 라이브러리가 준비되어 있기 때문에 실제로 굉장히 많은 하이 코더들이 이를 사용하고 있습니다. 이를 위해서 'Tools' - 'Compiler Options' 탭으로 이동합니다.



  이후에 다음과 같이 -std=c++11 컴파일 옵션을 적용합시다.


  -std=c++11

  이제 간단히 "Hello World!"를 출력하는 프로그램을 작성해보도록 하겠습니다.



#include <bits/stdc++.h>

using namespace std;

int main(void) {
	cout << "Hello World!";
	return 0;
}

  실행 결과는 다음과 같습니다.



※ #include <bits/stdc++.h>란? ※


  알고리즘 대회에서 가장 많이 사용되는 헤더 파일 중 하나가 바로 bits/stdc++.h입니다. 표준 라이브러리를 모두 포함하고 있는 헤더로서 이것을 사용하면 별도의 헤더를 추가적으로 넣지 않아도 됩니다. 다만 이 헤더는 GCC 전용 라이브러리이므로 GCC를 지원하는 대회 환경에서 사용해야 합니다. 다행히도 대부분의 대회 환경에서는 이를 지원합니다.


  이 헤더에 포함되어 있는 대표적인 라이브러리들은 다음과 같습니다.


  - #include <string>

  - #include <vector>

  - #include <memory>
  - #include <map>

  - #include <algorithm>

  - #include <queue>


  이외에도 정말 많이 사용되는 라이브러리들이 모두 포함되어 있으므로 시간 절약 및 숏코딩 측면에서 매우 유리하다고 할 수 있습니다. 한 번 벡터(Vector) 라이브러리를 이용해서 N개의 원소를 저장하여 출력하는 프로그램을 작성해보도록 합시다.

#include <bits/stdc++.h> using namespace std; int main(void) { int n; cin >> n; vector<int> a;

for(int i = 0; i < n; i++) { a.push_back(i); } for(int i = 0; i < n; i++) { cout << a[i] << ' '; } return 0; }


  실행 결과는 다음과 같습니다.




728x90
반응형

Comment +1

728x90
반응형

  코드포스 공식 사이트: https://codeforces.com/


  코드포스는 세계에서 가장 유명한 알고리즘 대회 사이트 중 하나입니다. 일반적으로 매 주마다 1회 이상의 대회가 열리며, 대회에 참여해서 문제를 풀면 자신의 성적에 따라서 레이팅(Rating)을 판정 받을 수 있습니다. 코드포스에 가입한 이후에 메인 화면(Home)으로 가보면 다음과 같이 다가 올 대회에 대한 정보가 오른쪽에 출력되며, 위쪽 내비게이션 바에서 대회 목록(Contests)에 들어가서 대회 정보를 확인할 수 있어요.



  대회 목록 페이지로 이동하면 다음과 같은 화면이 나옵니다. 위쪽에는 향후 다가올 대회에 대한 정보가 출력되고, 아래 쪽에는 최근까지 진행되었던 대회 정보가 출력됩니다.



  이 중에서 하나의 대회에 들어가서 확인해보도록 합시다. 그러면 다음과 같이 문제 목록이 출력되는 것을 확인할 수 있습니다. 이 중에서 원하는 문제를 선택해 문제를 풀 수 있습니다. 코드포스는 문제의 난이도가 쉬운 것부터 어려운 것 순서대로 나열되어 있다는 특징이 있습니다.



  특정한 문제를 선택해 들어가 보면 다음과 같은 형태로 문제에 대한 내용이 출력됩니다. 우리는 'SUBMIT CODE'를 눌러서 소스코드를 실제로 제출할 수 있고, 그에 대한 정답 확인은 'MY SUBMISSIONS' 탭에서 확인할 수 있습니다.



  또한 문제의 유형이나 점수 등에 대한 정보 [Problem Tags] 영역에서 확인할 수 있습니다. 이는 실제 대회가 진행되는 중에는 확인할 수 없고, 대회가 끝나고 나면 출제자의 의도 등을 확인할 수 있는 탭이에요. 또한 코드포스는 튜토리얼(Tutorial) 등에 대한 내용도 함께 제시됩니다. 완전히 정답 소스코드를 제공하는 것은 아니지만, 충분히 이해할 수 있는 수준에서의 해법을 알려준다는 특징이 있습니다.



  결과적으로 '코드 제출(SUBMIT CODE)' 버튼을 누르면 다음과 같이 코드를 제출할 수 있는 화면으로 넘어갑니다.



  소스코드를 제출한 이후에는 '나의 제출(MY SUBMISSIONS)' 탭에서 자신의 정답 여부를 확인할 수 있습니다. 코드포스는 정답이 틀린 경우, 정확히 어떠한 테스트(Test)에서 정답이 틀렸는지까지 알려준다는 특징이 있습니다. 물론 대회가 진행 중일 때는 알려주지 않지만요.



  또한 '순위(STANDINGS)' 탭에 가시면 다음과 같이 실시간으로 대회에 참여했던 참가자들의 순위 정보가 출력됩니다.



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