문제

준성이는 1㎝ 간격으로 눈금이 매겨져 있는 줄자를 가지고 있다. 그 줄자에 있는 서로 다른 눈금 6개에 한 눈금에 하나씩 점이 찍혀 있는데, 빨간 점, 파란 점, 노란 점이 각각 두 개씩 있다.

준성이는 먼저 빨간 점이 만나도록 줄자를 접었다. 그런 후 두 파란 점이 만나도록 줄자를 접고, 또 다시 두 노란 점이 만나도록 줄자를 접었다. 줄자는 투명하여 접더라도 점들을 잘 볼 수 있다. 어떤 색깔의 두 점이 만나도록 줄자를 접었을 때, 그 다음에 접으려는 색깔의 두 점이 이미 만나고 있으면, 그 두 점에 대해서는 줄자를 접지 않는다.

예를 들어 길이 10㎝ 인 줄자에 아래 그림과 같이 2㎝ 와 7㎝ 위에에 두 빨간 점이 찍혀 있고, 5㎝ 와 4㎝위치에 파란 점이, 10㎝ 와 3㎝ 위치에 노란 점이 찍혀 있다고 하자. (그림에서 빨간 점은 별표로, 파란 점은 동그라미, 그리고 노란 점은 네모로 표시되어 있다.) 빨간 두 점이 만나도록 줄자를 접으면 줄자의 4.5㎝ 위치에서 접히고 4㎝ 와 5㎝ 눈금이 서로 만나게 된다. 그러면 줄자의 왼쪽 부분의 길이는 4.5㎝ 이고 오른쪽 부분의 길이는 5.5㎝가 되어, 접힌 줄자의 길이는 5.5㎝ 가 된다. 파란 두 점은 이미 만나므로 줄자를 접지 않고, 그런 다음 노란 두 점이 만나도록 접으면 줄자의 길이는 3.5㎝ 가 된다.

줄자의 길이와 각 색깔의 점들이 찍혀있는 위치가 주어질 때, 준성이가 빨간 색, 파란 색, 노란 색의 순서로 두 점이 만나도록 줄자를 접으면 줄자의 길이가 얼마가 되는지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 줄자의 길이가 입력된다. 줄자의 길이는 10㎝ 이상, 1,000㎝ 이하이고 단위를 나타내는 ㎝은 입력되지 않는다. 둘째 줄에는 두 빨간 점의 위치를 나타내는 정수가 빈칸을 사이에 두고 입력된다. 셋째 줄에는 두 파란 점의 위치가, 넷째 줄에는 두 노란 점의 위치를 나타내는 정수가 빈칸을 사이에 두고 입력된다. 모든 점들의 위치는 서로 다르다.

출력

한 줄에 접은 후의 줄자의 길이를 소수점 이하 한자리까지 출력한다. 소수점 이하 한자리가 0 이면 0 도 출력한다.(예 4.0)

예제 입력 1 

10
2 7
5 4
10 3

예제 출력 1 

3.5

약간의 수학과 구현 알고리즘으로 해결할 수 있는 문제이다.

'접는다' 라는 개념이 낯설게 느껴져 다소 고민을 했었지만 차근차근 생각하면 된다.

먼저 접는 순서는 빨강 -> 파랑 -> 노랑의 순서를 가지며, 접은 후의 길이는 접힌 부분과 접히지 않는 부분의 길이 중 더 긴 길이를 채택한다.

예를 들어 문제와 같이 4.5를 기준으로 접을때 아래와 같은 모양이 될 것이다.

위는 기존의 위치이고, 아래는 접힌 부분을 표시한 것이다. 4.5~10까지의 길이가 더 길기 때문에 전체 종이의 길이는 10-4.5가 된다.

그럼 이제 점들의 좌표를 어떻게 변경할까의 문제이다.

문제의 예시를 기준으로 빨간점 (2,7)이 접혔을때의 중간지점(접히는 지점)을 알기 위해 두 수의 평균을 구한다.

=> (2 + 7 )/ 2 = 4.5

4.5라는 좌표를 기준으로 두 점을 접게되므로, 다른점들도 새로운 좌표로 이동하게 되는데 여기서 당연하게도 접히는 지점보다 오른쪽에 있는 수들은 움직이지 않고 위치가 고정될 것이다. 위 예시에서 파란점5, 빨간점7, 노란점10이 이에 해당한다.(4.5<5, 7, 10)

새로운 좌표는 대칭 이동이므로, 기준점(위 예시에서는 빨간색 점)들의 합에 맞춰 대칭이동을 수행하면 된다.

따라서 파란점 4는 9(2+7) - 4 한 값인 5로 이동하게 될 것이며, 노란점 3은 9 - 3 = 6이므로 좌표 6으로 이동하게 된다.

위 알고리즘을 적용한 다른 예시는 아래와 같다. 편의상 빨,파,노는 r,b,y로 적었다.

0 1 2 3 4 5 6 7 8 9 10
    b b   y y r r 

# r 접기
7+8 = 15, 중간점 7.5, 전체 길이 (10-7.5 = 2.5) < (7.5-0 = 7.5) => 7.5
7.5 8 9 10 11 12 13 14 15
    r y  y     b  b

# b 접기
12 + 13 = 25, 중간점 12.5, 전체 길이 (15-12.5 = 2.5) < (12.5-7.5 = 5) => 5
12.5 13 14 15 16 17 17.5
b           y  y

# y 접기
15 + 16 = 31, 중간점 15.5, 전체길이 (17.5-15.5=2) < (15.5-12.5=3) => 3

이 알고리즘을 코드로 옮기면 아래와 같다. 편의를 위해 반복문을 사용하여 중복을 최소화하였다.

start = 0 # 시작 좌표는 0
end = int(input()) # 끝 점의 좌표
length = end-start+1
colors = [list(map(int,input().split())) for _ in range(3)]
for i,color in enumerate(colors):
    # 만약 두 점의 좌표가 같다면 해당 색상에 대해서는 이동하지 않는다.
    if color[0] == color[1]:
        continue
    # 중간점 구하기
    color_sum = sum(color)
    mid = round(color_sum/2,1) # 소수점 첫째자리까지
    # 전체 길이 구하기
    length = max((end-mid),(mid-start))
    # 새로운 시작점, 끝점 구하기
    start = mid
    end = start + length
    # 좌표 이동
    # 현재 움직인 좌표 이후의 색에 대해서만
    for j in range(i,len(colors)):
        for k in range(2):
            if colors[j][k] < mid: # 중간점보다 왼쪽에 있는 경우에만 새로운 좌표로 움직인다.
                colors[j][k] = color_sum - colors[j][k]
print(length)

https://www.acmicpc.net/problem/2784

# https://www.acmicpc.net/problem/12018

# 목표 : 최대한 많은 과목을 듣는것
# 수강권을 얻는 방법 => 많이 투자한 순에서 해당 과목의 수강신청 인원만큼 받아줌
# => 가장 적절한 값으로 수강에 성공하는 것이 중요
# 
# 아이디어 : 다른 사람들이 입력한 가격을 내림차순으로 정렬
# 정렬한 가격들 중에서, 수강신청 인원의 마지막에 들어가는 것이 가장 적절한 가격
# 가장 이득을 보는 가격을 과목 가격 배열에 삽입
# 과목 가격 배열을 오름차순으로 정렬하고 앞에서부터 차례로 포인트가 만족하는한 과목을 담으면 된다.

import sys
input = sys.stdin.readline

n,m = map(int,input().split()) # 과목 수, 보유중인 마일리지 양

subject_price = [1]*n

for i in range(n):
    p,l = map(int,input().split()) # 신청한 사람 수,과목의 수강 인원
    data = list(map(int,input().split()))
    # 수강 가능 인원이 신청자 보다 많을 경우 => 1원만 입력해도 입찰이 가능
    if p<l:
        continue # 넘어감 => 1원
    data.sort(reverse=True) # 내림차순 정렬 => 위에서부터 컷
    # 적정 가격은 l-1번째 사람이 입찰한가격과 같은 값(같은 값이면 우선순위가 높으므로)
    subject_price[i] = data[l-1]

# 몇과목을 수강할 수 있는지 계산
count = 0 # 들을 수 있는 가격의 수
subject_price.sort()
for price in subject_price:
    if m-price >= 0: # 현재 마일리지에서 수강 가능하면
        count+=1 # 수강가능
        m-=price # 수강하기
    else:
        break # 더이상 못듣는다면 탐색 종료
print(count)

https://www.acmicpc.net/problem/12018

https://www.acmicpc.net/problem/3151

10
2 -5 2 3 -4 7 -4 0 1 -6

6

투 포인터와 이분 탐색을 활용하여 푸는 문제이다.

문제를 풀기 위한 기본적인 아이디어는 아래와 같다.

0. 먼저 배열을 오름차순으로 정렬한다.

1. 세개의 숫자 중 기준이 되는 한 숫자를 왼쪽에서 부터 결정한다. 편의상 이 수를 기준수라고 부르겠다.

2. 투 포인터를 활용하여 기준수의 오른쪽 수들중에서 숫자 2개를 결정한다.

두 수와 기준수를 더해서 0이 되어야 하므로, 두수의 합이 -기준수와 같아야 한다.

예를 들어 기준수가 -3이라면 나머지 두 수의 합은 3이어야 한다. 이 두 수를 결정하는 과정에서 투 포인터를 활용하며 예시를 들자면 아래와 같다.

-6 -5 -4 -4 0 1 2 2 3 7
select = -6; target = 6

start,end = 1,9 (배열의 index)
-5 + 7 = 2 < target ; start++
-4 + 7 = 3 < target ; start++
-4 + 7 = 3 < target ; start++
0 + 7 = 7 > target ; end--
0 + 3 = 3 < target ; start++
1 + 3 = 4 < target ; start++
2 + 3 = 5 < target ; start++
2 + 3 = 5 < target ; start++
start == end ; break

투 포인터 start와 end를 두고, 기준수의 오른쪽 부분 배열에서 왼쪽 끝과 오른쪽 끝을 각각 가리키게 한다.

start와 end가 가리키는 두 수를 더한 값이

target과 비교하여 더 작은 수라면

더 많이 더해야 한다는 의미이므로, start를 오른쪽으로 한칸 당긴다. 

target과 비교하여 더 큰 수라면

합을 조금 줄여야 한다는 의미이므로, end를 왼쪽으로 한칸 당긴다.

target과 비교하여 같은 수라면

같은 조건을 만족하는 수가 더 많이 있을 수 있으므로 추가 검증을 진행한다.

이 추가 검증 과정에서 추가적인 아이디어가 필요한데, 다음 예시를 통해 설명하겠다.

아래와 같은 배열이 있고, 기준수가 -8인 상황을 가정해보자.

start가 가리키는 수는 3으로 end는 5라면 data[start] + data[end] = 8로 우리가 찾고자 하는 수와 동일해진다.

배열을 살펴보면 5를 값으로 갖는 경우가 많이 등장하는데, 만약 start이후의 수가 모두 5인 경우를 상상해보면 end를 계속 -1해줘야 하므로 시간 복잡도는 결국 O(n)과 거의 동일해진다.

따라서 이러한 상황을 방지 하기 위해 bisect_left() 라이브러리를 활용하여 여러개의 5들 중 가장 왼쪽 인덱스에 해당하는 값을 알 수 있다면 end에서 그러한 인덱스를 빼주는 것으로 조건을 만족하는 전체 end의 수를 알 수 있다.

이번엔 아래와 같은 경우를 살펴보자.

기준수가 -10이고, start와 end는 각각 양 끝 값을 가리키고 있다.

배열은 정렬되어 있는 상황이므로, data[start]와 data[end]의 값이 같다면 추가적인 검증이 필요없이 start~end 사이의 값들도 모두 5라는 것을 알 수 있으므로, start가 1번째 인덱스인 상황에서 조건을 만족하는 end의 개수는 end-start개임을 알 수 있다.

이러한 규칙을 적용시키면서 start가 1에서 2,3,4, 등으로 옮겨가도록 하면 end포인터를 처음까지 당기는 연산을 수행 할 필요 없이 비교적 짧은 시간복잡도로 문제를 해결 할 수 있다.

이러한 아이디어를 코드로 옮기면 아래와 같다.

# https://www.acmicpc.net/problem/3151
'''
먼저 전체 데이터를 정렬
왼쪽에서 부터 수를 하나 지정, 해당 수와 더해서 0이 되도록하는 조건수 지정
해당 수의 오른쪽 수에서 부터 투포인터를 사용하여 투포인터를 통해 조건 수를 만들 수 있는지 확인
'''
import sys
from bisect import bisect_left
input = sys.stdin.readline
N = int(input())
data = list(map(int,input().split()))
data.sort()
result = 0 # 경우의 수(정답에 해당)
# 조건수 지정
for i in range(N-2):
    # i번째 수와 더해서 0이 될 수 있는 조건 수 지정
    target = -data[i]
    start,end = i+1,N-1 # 이분탐색의 양 끝점 지점(투 포인터 지정)
    while start<end:
        temp = data[start] + data[end]
        # 양 끝점을 더한 수가
        if temp == target:
            # 값이 같은 경우
            if data[start] == data[end]:
                result += (end-start)
            else: # 값이 다를 경우
                # 오른쪽에 해당하는 값의 개수만큼
                index = bisect_left(data,data[end]) # data[end]중 가장 왼쪽 인덱스 리턴
                result += end-index+1
            start+=1
        elif temp < target: 
            start+=1
        else: # temp > target
            end-=1

print(result)

https://www.acmicpc.net/problem/4485

다익스트라 알고리즘을 활용하여 풀 수 있는 문제이다.

테스트 케이스 1번을 예시로 설명해보겠다.

1. 시작 좌표로부터의 최단 거리를 저장하기 위한 2차원 배열을 별도로 생성하고, 배열의 값을 모두 INF로 초기화한다.

(INF는 아직 도달하지 못한 좌표를 의미하며 1e9로 값을 할당하였다.)

2. 최소 힙을 생성하여, 시작좌표(0,0)의 도둑 루피 값을 정렬 기준으로 최소힙에 삽입한다.

3. 최소 힙에서 가장 도둑 루피가 작은 값을 팝하여, 상하좌우 좌표를 검사한다.

아직 최소힙에 들어있는 값은 시작 좌표말고 없으므로, 시작 좌표의 값이 뽑힌다.

배열의 범위를 벗어나지 않으면서 현재 위치에서의 최단 비용과 이동할 위치의 최단 비용을 합친 값이, 기존 distance 배열에서의 값보다 작아진다면(우리는 최소 비용을 갖고 목적지에 도달하는것이 목표이므로) distance의 값을 갱신하고,

갱신한 값과 좌표를 최소 힙에 삽입한다.

4. 최소 힙에서 가장 도둑 루피가 작은 값을 팝하여, 상하좌우 좌표를 검사한다.

최소 힙에서 가장 비용이 적은 값은 8이므로, 8(1,0)이 뽑힌다.

(1,0) 좌표의 인접한 좌표 (0,0),(2,1),(1,1)은 누적 비용 8에 각각의 좌표에서의 도둑 루피 값을 더하면 13, 11, 17 이 되므로, (2,0), (1,1) 좌표의 distance배열의 값을 갱신하고 최소 힙에 삽입한다.

5. 최소 힙에서 가장 도둑 루피가 작은 값을 팝하여, 상하좌우 좌표를 검사한다.

최소 힙에서 가장 비용이 적은 값은 10이므로, 10(0,1)이 뽑힌다.

(0,1) 좌표의 인접한 좌표 (0,0),(0,2),(1,1)은 누적 비용 10에 각각의 좌표에서의 도둑 루피 값을 더하면 15,14,19 가 되므로,

(0,2) 좌표의 distance배열의 값을 갱신하고 최소 힙에 삽입한다.

6. 최소 힙에서 가장 도둑 루피가 작은 값을 팝하여, 상하좌우 좌표를 검사한다.

최소 힙에서 가장 비용이 적은 값은 11이므로, 11(2,0)이 뽑힌다.

(2,0) 좌표의 인접한 좌표 (1,0),(2,1)은 누적 비용 11에 각각의 좌표에서의 도둑 루피 값을 더하면 19,13이 되므로,

(2,1) 좌표의 distance배열의 값을 갱신하고 최소 힙에 삽입한다.

7.  최소 힙에서 가장 도둑 루피가 작은 값을 팝하여, 상하좌우 좌표를 검사한다.

최소 힙에서 가장 비용이 적은 값은 13이므로, 13(2,1)이 뽑힌다.

(2,1) 좌표의 인접한 좌표 (1,1),(2,2)은 누적 비용 13에 각각의 좌표에서의 도둑 루피 값을 더하면 22,20이 되므로,

(2,2) 좌표의 distance배열의 값을 갱신하고 최소 힙에 삽입한다.

목적지인 (2,2)에 도달하였으므로, 탐색을 종료하고 distance[n-1][n-1]값을 정답으로 출력한다.

위 아이디어를 코드로 옮기면 아래와 같다.

import heapq
INF = int(1e9)  # 무한 거리
t = 1  # 현재 몇번째 문제인지 기록
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]


def dijkstera():
    global distance
    queue = []  # 최소 힙으로 사용하기 위한 배열
    # 시작 좌표에서의 가격, 시작 좌표를 최소 힙에 삽입
    heapq.heappush(queue, (graph[0][0], 0, 0))
    while queue:
        dist, x, y = heapq.heappop(queue)  # 가장 코스트가 적은 노드 뽑기
        # 네 가지 방향에 대해서
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            # 범위를 벗어나지 않으면서
            if 0 <= nx < n and 0 <= ny < n:
                # 현재 점을 거쳐서 가면 더 짧아진다면 갱신
                if dist + graph[nx][ny] < distance[nx][ny]:
                    distance[nx][ny] = dist + graph[nx][ny]
                    # 최소힙에 푸쉬
                    heapq.heappush(queue, (distance[nx][ny], nx, ny))
                # 목적지에 도달하였다면
                if (nx, ny) == (n-1, n-1):
                    return


while True:  # 0이 입력될때까지 반복
    n = int(input())
    if n == 0:
        break
    graph = [list(map(int, input().split())) for _ in range(n)]
    # 각 좌표에 대한 최단 경로를 저장하기 위한 배열 생성
    distance = [[INF]*n for _ in range(n)]
    # 다익스트라 알고리즘 수행
    dijkstera()
    # 정답 출력
    print(f"Problem {t}:", distance[n-1][n-1])
    t += 1