IT-garden

문제

상근이는 나무 M미터가 필요하다. 근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다. 정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, 상근이는 새로 구입한 목재절단기를 이용해서 나무를 구할것이다.

목재절단기는 다음과 같이 동작한다. 먼저, 상근이는 절단기에 높이 H를 지정해야 한다. 높이를 지정하면 톱날이 땅으로부터 H미터 위로 올라간다. 그 다음, 한 줄에 연속해있는 나무를 모두 절단해버린다. 따라서, 높이가 H보다 큰 나무는 H 위의 부분이 잘릴 것이고, 낮은 나무는 잘리지 않을 것이다. 예를 들어, 한 줄에 연속해있는 나무의 높이가 20, 15, 10, 17이라고 하자. 상근이가 높이를 15로 지정했다면, 나무를 자른 뒤의 높이는 15, 15, 10, 15가 될 것이고, 상근이는 길이가 5인 나무와 2인 나무를 들고 집에 갈 것이다. (총 7미터를 집에 들고 간다)

상근이는 환경에 매우 관심이 많기 때문에, 나무를 필요한 만큼만 집으로 가져가려고 한다. 이때, 적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000)

둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M을 넘기 때문에, 상근이는 집에 필요한 나무를 항상 가져갈 수 있다. 높이는 1,000,000,000보다 작거나 같은 양의 정수 또는 0이다.

출력

적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 출력한다.

예제 입력과 출력

알고리즘 분류

이분 탐색

정답

n,m=map(int,input().split())
h=list(map(int,input().split()))

low=0
high=max(h)
r=0

while high >= low:
    mi=(low + high) // 2
    
    c = sum([i - mi if mi < i else 0 for i in h])

    if c >= m:
        low = mi + 1
        if r < mi:
            r = mi
    elif c < m:
        high = mi - 1

print(r)

백준 알고리즘 2805번 : https://www.acmicpc.net/problem/2805

문제

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N(1≤N≤100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1≤M≤100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다.

출력

M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

예제 입력과 출력

알고리즘 분류

이분 탐색 

정답

import sys

input = lambda :sys.stdin.readline().strip()

n=int(input())
a=list(map(int,input().split()))

m=int(input())
b=list(map(int,input().split()))
c=[0]*m

a.sort()

for i in range(m):
    low=0
    high=len(a)-1

    while low <= high:
        mi=(low+high) // 2

        if b[i] == a[mi]:
            c[i] =1
            break
        elif b[i] > a[mi]:
            low= mi+1
        elif b[i] < a[mi]:
            high =mi-1

for i in c:
    print(i)

백준 알고리즘 1920번 : www.acmicpc.net/problem/1920

문제

땅 위에 달팽이가 있다. 이 달팽이는 높이가 V미터인 나무 막대를 올라갈 것이다.

달팽이는 낮에 A미터 올라갈 수 있다. 하지만, 밤에 잠을 자는 동안 B미터 미끄러진다. 또, 정상에 올라간 후에는 미끄러지지 않는다.

달팽이가 나무 막대를 모두 올라가려면, 며칠이 걸리는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 세 정수 A, B, V가 공백으로 구분되어서 주어진다. (1 ≤ B < A ≤ V ≤ 1,000,000,000)

출력

첫째 줄에 달팽이가 나무 막대를 모두 올라가는데 며칠이 걸리는지 출력한다.

예제 입력과 출력

알고리즘 분류

수학
이분 탐색

정답

a, b, v=map(int,input().split())

r=(v-b)/(a-b)
print(int(r) if r == int(r) else int(r)+1)

반복문을 사용하니 시간초과가 나옵니다.

v-b를 통해 마지막 날에는 잠자는 것을 고려하지 않습니다.

백준 알고리즘 2869번 : https://www.acmicpc.net/problem/2869

문제

무게가 서로 다른 N 개의 물건이 있다. 각 물건은 1부터 N 까지 번호가 매겨져 있다. 우리는 일부 물건 쌍에 대해서 양팔 저울로 어떤 것이 무거운 것인지를 측정한 결과표를 가지고 있다. 이 결과표로부터 직접 측정하지 않은 물건 쌍의 비교 결과를 알아낼 수도 있고 알아내지 못할 수도 있다. 예를 들어, 총 6개의 물건이 있고, 다음 5개의 비교 결과가 주어졌다고 가정하자. ([1]은 1번 물건의 무게를 의미한다.)

[1]>[2], [2]>[3], [3]>[4], [5]>[4], [6]>[5]

우리는 [2]>[3], [3]>[4]로부터 [2]>[4]라는 것을 알 수 있다. 하지만, 물건 2와 물건 6을 비교하는 경우, 앞서의 결과만으로는 어느 것이 무거운지 알 수 없다. 이와 같이, 물건 2는 물건 1, 3, 4와의 비교 결과는 알 수 있지만, 물건 5, 6과의 비교 결과는 알 수 없다. 물건 4는 모든 다른 물건과의 비교 결과를 알 수 있다.

비교 결과가 모순되는 입력은 없다고 가정한다. 위 예제의 기존 측정 결과에 [3]>[1]이 추가되었다고 가정하자. 이 경우 [1]>[2], [2]>[3]이므로 우리는 [1]>[3]이라는 것을 예측할 수 있는데, 이는 기존에 측정된 결과 [3]>[1]과 서로 모순이므로 이러한 입력은 가능하지 않다.

물건의 개수 N 과 일부 물건 쌍의 비교 결과가 주어졌을 때, 각 물건에 대해서 그 물건과의 비교 결과를 알 수 없는 물건의 개수를 출력하는 프로그램을 작성하시오.

입력

첫 줄에는 물건의 개수 N 이 주어지고, 둘째 줄에는 미리 측정된 물건 쌍의 개수 M이 주어진다. 단, 5 ≤ N ≤ 100 이고, 0 ≤ M ≤ 2,000이다. 다음 M개의 줄에 미리 측정된 비교 결과가 한 줄에 하나씩 주어진다. 각 줄에는 측정된 물건 번호를 나타내는 두 개의 정수가 공백을 사이에 두고 주어지며, 앞의 물건이 뒤의 물건보다 더 무겁다.

출력

여러분은 N개의 줄에 결과를 출력해야 한다. i 번째 줄에는 물건 i 와 비교 결과를 알 수 없는 물건의 개수를 출력한다.

예제 입력과 출력

알고리즘 분류

플로이드 와샬 알고리즘 

정답

import sys

input=lambda : sys.stdin.readline().strip()

n=int(input())
m=int(input())

a=[[0] * (n+1) for i in range(n+1)]

for i in range(m):
    m1, m2=map(int, input().split())
    a[m1][m2] = 1

for k in range(1,n+1):
    for i in range(1,n+1):
        for j in range(1,n+1):
            if a[i][k] == 1 and a[k][j] == 1:
                a[i][j]=1

r=[]
for i in range(1,n+1):
    c= 0
    for j in range(1,n+1):
        if i == j:
            continue
        if a[i][j] + a[j][i] == 0:
            c += 1
    r.append(c)

for i in r:
    print(i)

백준 알고리즘 10159번 : www.acmicpc.net/problem/10159

문제

1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 6번만 키를 비교하였고, 그 결과가 다음과 같다고 하자.

• 1번 학생의 키 < 5번 학생의 키
• 3번 학생의 키 < 4번 학생의 키
• 5번 학생의 키 < 4번 학생의 키
• 4번 학생의 키 < 2번 학생의 키
• 4번 학생의 키 < 6번 학생의 키
• 5번 학생의 키 < 2번 학생의 키

이 비교 결과로부터 모든 학생 중에서 키가 가장 작은 학생부터 자신이 몇 번째인지 알 수 있는 학생들도 있고 그렇지 못한 학생들도 있다는 사실을 아래처럼 그림을 그려 쉽게 확인할 수 있다. a번 학생의 키가 b번 학생의 키보다 작다면, a에서 b로 화살표를 그려서 표현하였다.

1번은 5번보다 키가 작고, 5번은 4번보다 작기 때문에, 1번은 4번보다 작게 된다. 그러면 1번, 3번, 5번은 모두 4번보다 작게 된다. 또한 4번은 2번과 6번보다 작기 때문에, 4번 학생은 자기보다 작은 학생이 3명이 있고, 자기보다 큰 학생이 2명이 있게 되어 자신의 키가 몇 번째인지 정확히 알 수 있다. 그러나 4번을 제외한 학생들은 자신의 키가 몇 번째인지 알 수 없다.

학생들의 키를 비교한 결과가 주어질 때, 자신의 키가 몇 번째인지 알 수 있는 학생들이 모두 몇 명인지 계산하여 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 학생들의 수 N (2<=N<=500)과 두 학생 키를 비교한 횟수 M (0<=M<=N(N-1)/2)이 주어진다. 다음 M개의 각 줄에는 두 학생의 키를 비교한 결과를 나타내는 두 양의 정수 a와 b가 주어진다. 이는 번호가 a인 학생이 번호가 b인 학생보다 키가 작은 것을 의미한다. 

출력

자신이 키가 몇 번째인지 알 수 있는 학생이 모두 몇 명인지를 출력한다. 

예제 입력과 출력

알고리즘 분류

플로이드 와샬 알고리즘 

정답

import sys
input = lambda : sys.stdin.readline().strip()

INF=sys.maxsize

n,m=map(int,input().split())
li=[[0]*(n+1) for i in range(n+1)]

for i in range(m):
    a, b=map(int, input().split())
    li[a][b] = 1

for k in range(1,n+1):
    for i in range(1,n+1):
        for j in range(1,n+1):
            if i == j:
                continue
            
            if li[i][k] == 1 and li[k][j] == 1:
                li[i][j] = 1

r=0
for i in range(1,n+1):
    c = 0
    for j in range(1, n+1):
        c += li[i][j] + li[j][i] 
    if c == n-1: #자기빼고 다 아는 경우
        r += 1
print(r)

시간 초과로 PyPy3로 제출했습니다.

a 학생이 b 학생보다 작으면 li[a][b]에 1을 추가합니다.

플로이드 와샬 알고리즘을 통해 k를 거쳐서 키를 확인할 수 있으면 거리를 1로 바꿔줍니다.

li[i][j] + li[j][i]을 통해 i보다 j가 크거나 작은지 확인합니다.
자신을 제외한 다른 수들이 크거나 작은지 확인할 수 있으면 r에 1을 더해주고 전체 r을 출력합니다.

백준 알고리즘 2458번 : www.acmicpc.net/problem/2458

문제

송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. 맥주 한 박스에는 맥주가 20개 들어있다. 목이 마르면 안되기 때문에 50미터에 한 병씩 마시려고 한다.

상근이의 집에서 페스티벌이 열리는 곳은 매우 먼 거리이다. 따라서, 맥주를 더 구매해야 할 수도 있다. 미리 인터넷으로 조사를 해보니 다행히도 맥주를 파는 편의점이 있다. 편의점에 들렸을 때, 빈 병은 버리고 새 맥주 병을 살 수 있다. 하지만, 박스에 들어있는 맥주는 20병을 넘을 수 없다.

편의점, 상근이네 집, 펜타포트 락 페스티벌의 좌표가 주어진다. 상근이와 친구들이 행복하게 페스티벌에 도착할 수 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 t가 주어진다. (t ≤ 50)

각 테스트 케이스의 첫째 줄에는 맥주를 파는 편의점의 개수 n이 주어진다. (0 ≤ n ≤ 100).

다음 n+2개 줄에는 상근이네 집, 편의점, 펜타포트 락 페스티벌 좌표가 주어진다. 각 좌표는 두 정수 x와 y로 이루어져 있다. (두 값 모두 미터, -32768 ≤ x, y ≤ 32767)

송도는 직사각형 모양으로 생긴 도시이다. 두 좌표 사이의 거리는 x 좌표의 차이 + y 좌표의 차이 이다. (맨해튼 거리)

출력

각 테스트 케이스에 대해서 상근이와 친구들이 행복하게 페스티벌에 갈 수 있으면 "happy", 중간에 맥주가 바닥나면 "sad"를 출력한다. 

예제 입력과 출력

알고리즘 분류

BFS
DFS
플로이드 와샬 알고리즘

정답

import sys

INF = sys.maxsize
input = lambda: sys.stdin.readline().strip()
t=int(input())

while t :
    n=int(input())
    a=[list(map(int, input().split())) for i in range(n+2)]
    d=[[INF] * (n+2) for i in range(n+2)]
    
    for i in range(n+2):
        for j in range(n+2):
            if i == j :
                continue
            di=abs(a[i][0]-a[j][0]) + abs(a[i][1]-a[j][1])
    
            if di <= 1000:
                d[i][j] = 1

    for k in range(n+2):
        for i in range(n+2):
            for j in range(n+2):
                if d[i][j] > d[i][k] + d[k][j]:
                    d[i][j] = d[i][k] + d[k][j]
    
    if 0 <= d[0][n+1] < INF:
        print('happy')
    else:
        print('sad')
  
    t -= 1

리스트 a에 상근이네 집, 편의점, 펜타포트 락 페스티벌 좌표를 넣습니다.

각각 좌표들간의 거리를 구해서 1000이하이면 리스트 d에 1을 넣습니다.

플로이드 와샬 알고리즘 이용해 더 빠르게 갈 수 있으면 값을 바꿔줍니다.

시작에서 락 페스티벌까지 갈 수 있는 거리가 INF보다 작으면 happy를 출력하고 아니면 sad를 출력합니다.

백준 알고리즘 9205번 : https://www.acmicpc.net/problem/9205