[코드포스] Codeforces Round #637 (Div. 2)

대회 링크: 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")