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

 

1946번: 신입 사원

첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성

www.acmicpc.net


풀이 과정


  1. 지원자 A의 성적이 어떤 지원자 B보다 서류 심사, 면접 성적이 모두 떨어지는 경우는 선발되지 않는다라는 조건이 있으므로, 따라서 서류 심사를 기준으로 오름차순 정렬을 해 준다.
  2. 정렬된 리스트를 기준으로 순차적으로 지원자를 검사한다.
    1. 서류 심사를 기준으로 오름차순 정렬을 해주었으므로, 서류심사 성적은 무조건 이전 지원자보다 안좋다고 볼 수 있으므로, 면접 성적만을 보면 된다.
    2. 따라서, 이전 지원자들보다 면접 성적이 좋아야만 합격이다. 따라서, 합격한 지원자들의 면접 성적중 가장 좋은 면접 성적보다 좋은지 확인하고, 좋다면 가장 좋은 면접 성적을 갱신하고 합격 카운팅을 해준다.
  3. 전체 합격자의 수를 출력한다.

소스 코드


import sys

input = lambda: sys.stdin.readline().rstrip()
T = int(input())

for _ in range(T):
    N = int(input())
    applicants = [list(map(int, input().split())) for _ in range(N)]
    applicants.sort()
    max_r2 = 999999
    answer = 0
    for _, r2 in applicants:
        if r2 < max_r2:
            max_r2 = r2
            answer += 1

    print(answer)

  

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

 

2638번: 치즈

첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로

www.acmicpc.net

 


풀이 과정


  1. 전체적으로 3가지 과정을 반복한다.
    1. 치즈가 더이상 남아있지 않은지 체크한다
    2. 외부 공기의 위치들을 따로 구해준다.
      • 이 과정에서 테두리는 무조건 외부 공기로 간주해도 되기 때문에, (0, 0)에서부터 1이 아닌 0을 만나는 경우에 대해서만 BFS를 진행해주면 된다.
    3. 각각의 치즈와 인접한 4개의 칸 중 몇개의 칸이 외부 공기인지 개수를 구하고, 2개 이상이라면 제거해 준다. 이 때, 한번에 제거해 주어야 제거로 인해 다른 치즈가 영향을 받지 않는다.
    4. 시간을 1초 증가시켜 준다.
  2. 치즈가 남아있지 않는다면, 총 몇초가 지났는지 출력시켜 준다.

소스 코드


import sys
from collections import deque

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

N, M = map(int, input().split())
matrix = [list(map(int, input().split())) for _ in range(N)]

dx = [-1, 1, 0, 0]
dy = [0, 0, 1, -1]

def get_air_pos():
    air = set()
    air.add((0, 0))
    queue = deque([[0, 0]])
    
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx and nx < N and 0 <= ny and ny < M:
                if (nx, ny) not in air and matrix[nx][ny] == 0:
                    air.add((nx, ny))
                    queue.append([nx, ny])

    return air

def is_empty():
    for i in range(N):
        for j in range(M):
            if matrix[i][j] != 0:
                return False
    return True

def destroy_cheese(air):
    destroy_cheese_pos = []
    for i in range(N):
        for j in range(M):
            if matrix[i][j] == 1:
                air_count = 0
                for k in range(4):
                    x, y = i + dx[k], j + dy[k]
                    if (x, y) in air:
                        air_count += 1
                if air_count >= 2:
                    destroy_cheese_pos.append([i, j])
                    
    for x, y in destroy_cheese_pos:
        matrix[x][y] = 0
                            

time = 0
while True:
    if is_empty():
        break
    air = get_air_pos()
    destroy_cheese(air)
    time += 1
    

print(time)

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

 

1058번: 친구

지민이는 세계에서 가장 유명한 사람이 누구인지 궁금해졌다. 가장 유명한 사람을 구하는 방법은 각 사람의 2-친구를 구하면 된다. 어떤 사람 A가 또다른 사람 B의 2-친구가 되기 위해선, 두 사람

www.acmicpc.net


풀이 과정


  1. 2-친구가 되기 위해서는 간단하게 보면 직접 친구이거나, 한명의 친구를 거쳐서 친구이면 된다. 따라서 플로이드 알고리즘을 사용하여 거리 배열을 구한다.
    1. 직접 친구인 경우의 거리는 1이다.
    2. 한명의 친구를 거쳐서 친구인 경우의 거리는 2이다.
  2. 각 사람별로 거리가 2 이하인 친구의 명수를 구해준 다음 최댓값을 구해준다.
  3. (2)에서 구한 최댓값을 출력해 준다.

소스 코드


import sys

input = lambda: sys.stdin.readline().rstrip()
N = int(input())

matrix = [list(input()) for _ in range(N)]
for i in range(N):
    for j in range(N):
        if matrix[i][j] == 'N':
            matrix[i][j] = int(10e9)
        else:
            matrix[i][j] = 1

for i in range(N):
    for j in range(N):
        for k in range(N):
            matrix[j][k] = min(matrix[j][k], matrix[j][i] + matrix[i][k])

answer = 0
for i in range(N):
    count = 0
    for j in range(N):
        if j != i and matrix[i][j] <= 2:
            count += 1
    answer = max(answer, count)


print(answer)

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

 

2456번: 나는 학급회장이다

첫째 줄에는 반의 학생들의 수 N (3 ≤ N ≤ 1,000)이 주어진다. 다음 N개의 각 줄에는 각 학생이 제출한 회장후보 3명에 대한 선호 점수가 주어지는 데, 첫 번째 점수는 후보 1번에 대한 점수이고 두

www.acmicpc.net


풀이 과정


문제에서 어떻게 구현하라고 다 나와있기 때문에 그대로 구현해주면 된다. 여기서는 개인적으로는 map과 filter을 잘 사용하면 소스코드가 많이 간결해질 수 있을 것이라고 생각된다.

  1. 각 후보가 점수별로 몇점을 획득하였는지 저장해 둔다.
  2. 전체 점수의 합계가 가장 큰 후보군을 먼저 골라준다.
  3. 후보군이 2명 이상인 경우에는 다음 단계로 진행한다.
    1. 3점을 가장 많이 받은 사람의 집합으로 후보군을 줄여준다.
    2. 이후, 2점을 가장 많이 받은 사람의 집합으로 후보군을 줄여준다.
  4. 모든 단계를 거치고 난 다음에도 후보군이 2명 이상이라면 0과 최대 점수를 출력해 주고, 후보군이 1명이라면 해당 인원의 번호와 점수를 출력해 준다.

소스 코드


import sys

input = lambda: sys.stdin.readline().rstrip()
N = int(input())

score = [[0] * 3 for _ in range(3)]

for _ in range(N):
    a, b, c = map(int, input().split())
    score[0][a-1] += a
    score[1][b-1] += b
    score[2][c-1] += c

total_score = [[idx, sum(sc)] for idx, sc in enumerate(score)]
max_score = max(map(lambda x: x[1], total_score))
candidate = list(filter(lambda x: x[1] == max_score, total_score))

if len(candidate) >= 2:
    max_three_count = max(map(lambda x: score[x[0]][2], candidate))
    candidate = list(filter(lambda x: score[x[0]][2] == max_three_count, candidate))
    max_two_count = max(map(lambda x: score[x[0]][1], candidate))
    candidate = list(filter(lambda x: score[x[0]][1] == max_two_count, candidate))

if len(candidate) >= 2:
    print(0, max_score)
else:
    print(candidate[0][0] + 1, candidate[0][1])

'알고리즘[Python] > 백준 알고리즘' 카테고리의 다른 글

[ 2638 ] [ BFS ] 치즈  (0) 2022.01.14
[ 1058 ] [ Floyd ] 친구  (0) 2022.01.13
[ 16398 ] [ Kruskal ] 행성 연결  (0) 2022.01.09
[ 2688 ] [ DP ] 줄어들지 않아  (0) 2022.01.06
[ 1826 ] [ Greedy ] 연료 채우기  (0) 2022.01.05

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

 

16398번: 행성 연결

홍익 제국의 중심은 행성 T이다. 제국의 황제 윤석이는 행성 T에서 제국을 효과적으로 통치하기 위해서, N개의 행성 간에 플로우를 설치하려고 한다. 두 행성 간에 플로우를 설치하면 제국의 함

www.acmicpc.net


풀이 과정


  1. Kruskal 알고리즘을 사용하여 최소 비용 신장 트리를 구성한다.
    1. 최소 비용인 간선을 하나 선택하고 Cycle을 형성하는지 체크한다
    2. Cycle을 형성하는지 체크하는 방법은 간선에 연결된 두 점이 하나의 집합에 속해있는지 확인하면 된다.
      1. Union-find 알고리즘 사용
    3. Cycle을 형성하지 않는다면 두 점을 연결해 주고 비용을 더해준다.
    4. 위 과정을 총 N-1개의 간선을 선택할 때까지 반복해 준다.
  2. 최소 비용 신장 트리의 비용의 합계를 출력시켜 준다.

풀이 과정


import sys
import heapq

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

N = int(input())
heap = []
cost = [list(map(int,input().split())) for _ in range(N)]

def find(parent, a):
    if parent[a] != a:
        parent[a] = find(parent, parent[a])
    return parent[a]

def union(parent, a, b):
    p1 = find(parent, a)
    p2 = find(parent, b)
    if p1 != p2:
        parent[p1] = p2

for i in range(N):
    for j in range(i+1, N):
        heapq.heappush(heap, [cost[i][j], i, j])

answer = 0
parent = [i for i in range(N+1)]
edge_count = 0
while heap and edge_count < N-1:
    cost, fr, to = heapq.heappop(heap)
    if find(parent, fr) != find(parent, to):
        union(parent, fr, to)
        answer += cost
        edge_count += 1


print(answer)

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

 

2688번: 줄어들지 않아

첫째 줄에 테스트 케이스의 개수 T(1 <= T <= 1,000)이 주어진다. 각 테스트 케이스는 숫자 하나 n으로 이루어져 있다. (1 <= n <= 64)

www.acmicpc.net

 


풀이 과정


  1. 맨 앞자리에 K가 들어오려면 이전 자리에는 K~9가 들어올 수 있다.
    1. 따라서 점화식을 구성하면 DP[i][K] = DP[i-1][K] + DP[i-1][K+1] + ... + DP[i-1][9]
    2. 해당 점화식을 이용하여 DP 테이블을 채워주면 된다. 단, 한자리일때는 자기 자신을 고를때밖에 없으므로 1로 설정하여 준다.
  2. 이후 각각의 테스트 케이스에 입력받은 자리수에 맞추어서 DP 테이블에서의 합계를 구해서 출력시켜 준다.
    • 예를 들어, 자릿수 4를 입력받으면 DP[4]의 합계를 출력시켜 주면 된다.

소스 코드


import sys

input = lambda: sys.stdin.readline().rstrip()
dp = [[0] * 10 for _ in range(65)]

for i in range(10):
    dp[1][i] = 1

for i in range(2, 65):
    for j in range(10):
        for k in range(j, 10):
            dp[i][j] += dp[i-1][k]

T = int(input())
for _ in range(T):
    C = int(input())
    print(sum(dp[C]))

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

 

1826번: 연료 채우기

첫째 줄에 주유소의 개수 N(1 ≤ N ≤ 10,000)가 주어지고 두 번째 줄부터 N+1번째 줄 까지 주유소의 정보가 주어진다. 주유소의 정보는 두개의 정수 a,b로 이루어 져 있는데 a(1 ≤ a ≤ 1,000,000)는 성경

www.acmicpc.net


풀이 과정


  1. 현재 가진 연료로 어떤 주유소를 들릴 수 있는지를 업데이트 해주는게 핵심
  2. 현재 가진 연료로 마을까지 갈 수 없다면 주유소를 무조건 하나 이상 들려야 함. 
    1. 따라서, 방문할 수 있는 주유소를 따로 기름의 양을 기준으로 최대 히프에 넣어 관리한다. 
    2. 이 때, 방문할 수 있는 주유소들 중 기름을 가장 많이 넣을 수 있는 주유소를 하나 방문해서 들려준다. 즉, 최대 히프에서 하나의 요소를 꺼내서 기름을 채워준다. 이 때 해당 주유소를 들리게 되므로 따로 카운트를 하나 늘려준다.
    3. 주유소를 방문해서 기름을 넣었으므로 넣은 기름으로 더 이동해서 방문할 수 있는 주유소를 다시 최대 히프에 넣어준다.
  3. 방문할 수 있는 주유소가 더이상 없는데 마을에 도착하지 않았다면 -1을 리턴해 주고, 마을에 도착하였다면 방문한 주유소의 수를 출력시켜 준다.

소스 코드


import sys
import heapq
from collections import deque

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

N = int(input())
stations = [list(map(int, input().split())) for _ in range(N)]
dist, current_gas = map(int, input().split())
heap = []

stations.sort(key=lambda x:x[0])
queue = deque(stations)

answer = 0
while True:
    while queue and queue[0][0] <= current_gas:
        _, gas  = queue.popleft()
        heapq.heappush(heap, -gas)

    if dist <= current_gas:
        break
    else:
        if not heap:
            answer = -1
            break
        append_gas = -heapq.heappop(heap)
        current_gas += append_gas
        answer += 1

print(answer)

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

 

1339번: 단어 수학

첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대

www.acmicpc.net

 


풀이 과정


  1. 각각의 알파벳이 있는 자리가 1이라고 할 때 모두 더했을때 값이 얼마나 나오는지 구한다.
    • 예를 들어, Axxxx + xxAxx라 하면 10100이 나온다.
  2. (1)에서 구한 값들중 가장 큰 값에 9를 부여하고, 다음 큰 값에 8을 부여하고 , .. 이러한 방식으로 값을 부여해준 다음 합계를 구해 준다.
    1. 값을 부여할 때는, (1)에서 구한 값에 부여한 값을 곱해주면 된다.
    2. 값을 부여한 후, 그대로 더한다.
  3. (2)에서 구한 합계를 출력해 준다.

소스 코드


import sys
from collections import defaultdict

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


alpha = defaultdict(lambda: 0)
N = int(input())
for _ in range(N):
    word = input()
    size = len(word)
    for idx, ch in enumerate(word):
        alpha[ch] += (10 ** (size-1-idx))

temp = sorted(alpha.values(), reverse=True)
pos = 0
answer = 0
for i in range(9, 0, -1):
    answer += temp[pos] * i
    pos += 1
    if pos == len(temp):
        break

print(answer)

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

 

16918번: 봄버맨

첫째 줄에 R, C, N (1 ≤ R, C, N ≤ 200)이 주어진다. 둘째 줄부터 R개의 줄에 격자판의 초기 상태가 주어진다. 빈 칸은 '.'로, 폭탄은 'O'로 주어진다.

www.acmicpc.net


풀이 과정


  1. 초기에 설치해둔 폭탄의 위치를 저장해 둔다.
  2. 폭탄이 없는곳에 모두 폭탄을 설치시켜 준다.
    • 이 때, 초기에 설치해둔 폭탄과 터지는 시간이 다르기 때문에 폭탄이 없는곳에 폭탄을 설치하면서 위치를 따로 저장해 두어야 한다.
  3. 직전에 설치한 폭탄이 아닌, 더 이전에 설치해둔 폭탄을 터트린다.
    • 이 때, 직전에 설치한 폭탄도 터질 수 있으므로 만약 직전에 설치한 폭탄도 터진다면 직전에 설치한 폭탄 집합에서 해당 폭탄을 제거해 준다.
  4. 입력받은 시간에 맞추어서 2-3 과정을 반복해 주면 된다.

소스 코드


import sys

input = lambda: sys.stdin.readline().rstrip()
R, C, N = map(int, input().split())

matrix = [list(input()) for _ in range(R)]
boompos = []
for i in range(R):
    for j in range(C):
        if matrix[i][j] == 'O':
            boompos.append([i, j])

def set_boom(matrix):
    next_boom = set()
    for i in range(R):
        for j in range(C):
            if matrix[i][j] == '.':
                next_boom.add((i, j))
                matrix[i][j] = 'O'
    return next_boom

def boom(matrix, boompos, next_boom):
    dx = [-1, 1, 0, 0]
    dy = [0, 0, 1, -1]
    destroypos = set()
    for x, y in boompos:
        destroypos.add((x, y))
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx and nx < R and 0 <= ny and ny < C:
                destroypos.add((nx, ny))

    for x, y in destroypos:
        if (x, y) in next_boom:
            next_boom.remove((x, y))
        matrix[x][y] = '.'
        

time = 1
while time < N:
    next_boom = set_boom(matrix)
    time += 1
    if time == N:
        break
    boom(matrix, boompos, next_boom)
    boompos = next_boom
    time += 1

for m in matrix:
    print("".join(m))

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

 

17352번: 여러분의 다리가 되어 드리겠습니다!

선린월드에는 N개의 섬이 있다. 섬에는 1, 2, ..., N의 번호가 하나씩 붙어 있다. 그 섬들을 N - 1개의 다리가 잇고 있으며, 어떤 두 섬 사이든 다리로 왕복할 수 있다. 어제까지는 그랬다. "왜 다리

www.acmicpc.net

 


풀이 과정


  1. 문제에서 다리를 하나 무너뜨려 서로 왕복할 수 없는 섬이 생겼다고 주어졌으므로 두개의 섬으로 분리되었다는걸 알 수 있음.
  2. Union-Find 알고리즘을 사용하여 두개의 섬의 집합을 구해준다.
    1. 이어진 섬의 parent는 같으며, 이어지지 않은 섬의 parent는 다르다는 점을 이용하여 1번째 섬에서부터 N번째 섬까지 방문하면서 인접한 섬과의 parent를 비교한다.
    2. parent 값이 다른 경우 떨어진 섬이므로 두 섬을 연결해주면 된다.

소스 코드


import sys

sys.setrecursionlimit(10**5)
input = lambda: sys.stdin.readline().rstrip()
N = int(input())
parent = [i for i in range(N+1)]


def find(parent, a):
    if parent[a] != a:
        parent[a] = find(parent, parent[a])
    return parent[a]

def union(parent, a, b):
    par1 = find(parent, a)
    par2 = find(parent, b)

    if par1 != par2:
        parent[par1] = par2

for _ in range(N-2):
    a, b = map(int, input().split())
    if find(parent, a) != find(parent, b):
        union(parent, a, b)

for i in range(2, N+1):
    if find(parent, i) != find(parent, i-1):
        union(parent, i, i-1)
        print(i, i-1)

+ Recent posts