졍's 기술 블로그

수열 걷기

티어 : Silver 1
시간 제한 : 1 초
메모리 제한 : 128 MB
알고리즘 분류 : 구현, 두 포인터

문제

길이가 유한하고, 오름차순 순서로 되어있는 두 수열이 주어진다. 두 수열에 공통으로 들어있는 원소는 교차점으로 생각할 수 있다.

아래는 두 수열과 교차점은 굵게 나타낸 것이다.

수열 1 = 3 5 7 9 20 25 30 40 55 56 57 60 62

수열 2 = 1 4 7 11 14 25 44 47 55 57 100

이 두 수열은 다음과 같이 걸을 수 있다.

1. 두 수열중 하나의 첫 번째 원소에서 걷기를 시작한다. 걷는 것은 앞으로만 걸을 수 있다.
2. 교차점에 도착했을 때는, 현재 수열에서 계속 걸을지, 다른 수열로 갈아탈지 결정할 수 있다.

방문한 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하시오. 위의 예에서 3, 5, 7, 9, 20, 25, 44, 47, 55, 56, 57, 60, 62와 같이 걷는다면 합이 450으로 최대가 된다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 두 줄로 이루어져 있다.

각 줄의 첫 번째 수는 수열의 길이이다. 그 다음에는 수열의 원소가 순서대로 주어진다. 수열의 길이는 1이상이고, 10,000을 넘지 않는다. 수열에 들어있는 모든 수는 -10,000보다 크거나 같고, 10,000보다 작거나 같은 정수이다.

입력의 마지막 줄에는 0이 하나 주어진다.

출력

각 테스트 케이스에 대해서, 얻을 수 있는 최대 합을 출력한다.

예제 입출력

Algorithm

이진 탐색 - bisect
1. bisect를 이용해 수열1과 수열2의 같은 값 찾기
2. 같은 수를 찾으면 각 수열에서 해당 숫자 이전까지의 합 구하기
3. answer에 각 수열의 합 중 최댓값 저장

Code

import sys
from bisect import bisect_left, bisect_right
input = sys.stdin.readline

while True:
    # 입력
    sequence1 = list(map(int, input().split()))
    # 0이 하나 주어지면 break
    if sum(sequence1) == 0:
        break
    seq1_len = sequence1[0]
    sequence1 = sequence1[1:]
    sequence2 = list(map(int, input().split()))
    seq2_len = sequence2[0]
    sequence2 = sequence2[1:]

    answer = 0
    index1 = 0 # 수열 1의 동일한 숫자의 index
    index2 = 0 # 수열 2의 동일한 숫자의 index
    for num in sequence1:
        # 동일한 숫자가 있으면
        if bisect_right(sequence2, num) - bisect_left(sequence2, num) > 0:
            # 첫 번째 수열의 해당 숫자까지의 합
            sum_seq1 = sum(sequence1[index1:bisect_right(sequence1, num)])
            # 두 번째 수열의 해당 숫자까지의 합
            sum_seq2 = sum(sequence2[index2:bisect_right(sequence2, num)])
            
            # 각 수열의 누적합 중 큰 값을 answer에 누적합
            answer += max(sum_seq1, sum_seq2)
            
            # 각 수열의 inex 갱신
            index1 = bisect_right(sequence1, num)
            index2 = bisect_right(sequence2, num)

    # 마지막 길의 최댓값 구해 answer에 추가
    answer += max(sum(sequence1[index1:]), sum(sequence2[index2:]))
    print(answer)

메모리: 33948 KB
시간: 100 ms

먹을 것인가 먹힐 것인가

티어 : Silver 3
시간 제한 : 1 초
메모리 제한 : 256 MB
알고리즘 분류 : 

문제

심해에는 두 종류의 생명체 A와 B가 존재한다. A는 B를 먹는다. A는 자기보다 크기가 작은 먹이만 먹을 수 있다. 예를 들어, A의 크기가 {8, 1, 7, 3, 1}이고, B의 크기가 {3, 6, 1}인 경우에 A가 B를 먹을 수 있는 쌍의 개수는 7가지가 있다. 8-3, 8-6, 8-1, 7-3, 7-6, 7-1, 3-1.

두 생명체 A와 B의 크기가 주어졌을 때, A의 크기가 B보다 큰 쌍이 몇 개나 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 A의 수 N과 B의 수 M이 주어진다. 둘째 줄에는 A의 크기가 모두 주어지며, 셋째 줄에는 B의 크기가 모두 주어진다. 크기는 양의 정수이다. (1 ≤ N, M ≤ 20,000) 

출력

각 테스트 케이스마다, A가 B보다 큰 쌍의 개수를 출력한다.

예제 입출력

Algorithm

1. bisect_left 이용
2. bisect_left()의 x값을 본인으로 했을 때의 반환값이 현재 index의 값이 먹을 수 있는 먹이 수
3. 반환되는 값 누적 합해 출력

Code

import sys
from bisect import bisect_left

input = sys.stdin.readline

# 입력
T = int(input())
for _ in range(T):
    _, _ = map(int, input().split())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    
    # B 정렬
    B.sort()
    
    answer = 0
    for i in A:
        # B List에서 A의 보다 작은 원소의 개수 누적합
        answer += bisect_left(B, i)
    print(answer)

메모리: 353116 KB
시간: 172 ms