태야

www.acmicpc.net/problem/2667

<내 코드>

from collections import deque


def bfs(x, y):
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
    cnt = 0
    queue = deque()

    queue.append((x, y))
    maps[x][y] = '0'
    done.append((x, y))

    while queue:
        now = queue.popleft()
        cnt += 1

        for i in range(4):
            nx = now[0] + dx[i]
            ny = now[1] + dy[i]

            if(0 <= nx < N) and (0 <= ny < N):
                if maps[nx][ny] == '1' and ((nx, ny) not in done):
                    maps[nx][ny] = '0'
                    queue.append((nx, ny))
                    done.append((nx, ny))
    return cnt


N = int(input())
maps = [list(input()) for _ in range(N)]
done = []
total = 0
result = []


for i in range(N):
    for j in range(N):
        if maps[i][j] == '1':
            result.append(bfs(i, j))
            total += 1

result.sort()
print(total)
for i in range(total):
    print(result[i])

크게 어려움 없이 BFS 알고리즘만 구현하면 쉽게 풀리는 문제였다. 각 BFS마다 total과 cnt 값을 올려줘 총 몇 번의 BFS 탐색을 했고, 각 탐색 중 몇 번의 인접한 요소들을 찾아냈는지 표시했다. 그리고 그 값들을 출력해주면 끝이다.

<내 코드>

from collections import deque


def bfs():
    direction = [(1, 0), (-1, 0), (0, 1), (0, -1)]

    while queue:

        now = queue.popleft()

        for i in range(4):
            nx = now[0] + direction[i][0]
            ny = now[1] + direction[i][1]

            if(0 <= nx < N) and (0 <= ny < M):
                if tomato[nx][ny] == 0:
                    tomato[nx][ny] = tomato[now[0]][now[1]] + 1 # 현재 요소 값에서 +1
                    queue.append((nx, ny))


M, N = map(int, input().split())
queue = deque()
tomato = []

# 토마토 상자 배열
for _ in range(N):
    tomato.append(list(map(int, input().split())))

# 값이 1인 요소들을 큐에 다 담기(동시 진행을 위한)
for i in range(N):
    for j in range(M):
        if tomato[i][j] == 1:
            queue.append((i, j))

# 탐색 시작
bfs()

ans = 0
for i in range(N):
    for j in range(M):
        if ans < tomato[i][j]:
            ans = tomato[i][j]
        if tomato[i][j] == 0:
            print(-1)
            exit()
        ans = max(ans, 1) # 1과 배열의 최대값과 비교
print(ans - 1)

기존 BFS 문제를 풀던 거보다 조금 더 복잡한 문제였다. 이번 문제는 BFS 탐색 안에서 큐에 값을 넣고 또 탐색 전에 미리 큐에 좌표를 넣어주는 문제였다. 그렇게 해서 값이 1인 좌표값들을 동시에 탐색하도록 하는 것이다. 

<내 코드>

from collections import deque


def bfs(x, y):
    direction = [(1, 0), (-1, 0), (0, 1), (0, -1),
                 (1, 1), (1, -1), (-1, 1), (-1, -1)]

    queue = deque() #탐색을 하려는 좌표를 담는다.
    queue.append((x, y))

    maps[x][y] = 0

    while queue:
        now = queue.popleft()

        for i in range(8): #상하좌우 대각선까지 탐색
            nx = now[0] + direction[i][0]
            ny = now[1] + direction[i][1]

            if(0 <= nx < h) and (0 <= ny < w):
                if maps[nx][ny] == 1:
                    maps[nx][ny] = 0
                    queue.append((nx, ny))


while True:

    w, h = map(int, input().split())
    maps = []
    cnt = 0

    if w == 0 and h == 0:
        break

    for _ in range(h):
        tmp = list(map(int, input().split()))
        maps.append(tmp)

    for i in range(h):
        for j in range(w):
            if maps[i][j] != 0:
                cnt += 1
                bfs(i, j)

    print(cnt)

1. w, h, 지도를 입력받는다.

2. 매 입력마다 BFS 탐색을 마치면 cnt를 +1 해준다.

3. BFS를 상하좌우 그리고 대각선까지 여덟 방향을 다 탐색한다.

4. 탐색 중 지도에서 1인 값을 0으로 바꾸고 큐에 좌표를 넣고 탐색을 반복한다.

<내 코드>

N = int(input())

weights = [int(input()) for _ in range(N)]
weights.sort(reverse=True)  # 내림차순


for i in range(N):
    weights[i] = weights[i] * (i+1)

print(max(weights))

문제 접근 방법

- 로프를 병렬로 연결하면 각 로프에는 w/k만큼의 동일한 중량이 걸린다.

- 즉, 가장 작은 무게를 들 수 있는 로프가 들 수 있는 질량 * 병렬연결 로프 개수 = 최종 무게

- 가장 무거운 무게를 들 수 있는 로프부터 내림차순으로 정렬한다.

처음에는 너무 어렵게 접근해서 복잡하게 생각했다. 그래서 디큐를 활용해 하나씩 빼고 넣고 하려고 했다가 실패했다. 이렇게 단순하게 풀릴지는... 후..

<내 코드>

T = int(input())

A, B, C = 0, 0, 0

while T > 0:
    if T >= 300:
        A = (T // 300)
        T = (T % 300)
    if (T >= 60) and (T < 300):
        B = (T // 60)
        T = (T % 60)
    if (T < 60):
        C = (T // 10)
        if (T % 10) == 0:
            print("{} {} {}".format(A, B, C))
            break
        else:
            print(-1)
            break

특별히 어려운 조건이 없는 문제였다. 최소한의 버튼 클릭 수를 구하기 위해 입력값을 큰 값으로 최대한 나누면 된다. 입력 값이 단위별로 나눌 수 있는 값인지 판단 후 계산을 하고 몫을 출력해주면 된다. 마지막에 10초로 나눴을 때 나머지가 0이 아니면 -1을 출력한다.

<내 코드>

def recruit(num, score):
    min_interview = score[0][1] # 첫번째 지원자 면접 등수
    cnt = 1 # 첫 번째 지원자는 서류점수가 1등이기에 무조건 뽑힘
    for i in range(1, num):  # 1번 ~ n-1번

        if score[i][1] < min_interview:  # 뽑히는 경우
            min_interview = score[i][1] # 더 높은 등수로 변경
            cnt += 1

    return cnt


tests = int(input())

for _ in range(tests):
    num = int(input())
    score = [list(map(int, input().split())) for _ in range(num)]
    score.sort(key=lambda x: x[0])  # 서류 시험 등수 오름차순
    print(recruit(num, score))

Python3로 제출하면 시간 초과가 나고, pypy로 제출하니 통과가 됐다. for문을 최대로 줄이려고 해 봤지만 다른 방법을 찾기가 쉽지 않았다.

문제 조건

- 다른 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발.

- 즉, 현재 지원자의 서류 성적보다  더 높은 서류 성적을 가진 사람들보다 면접 성적이 높아야 선발된다.

따라서 우선 성적을 '서류 성적순'으로 정렬시킨다. 그리고 가장 높은 서류 성적을 가진 사람은 면접이 낮더라도 무조건 선발된다. 그래서 첫 번째 지원자의 면접 성적을 min_interview에 담고 그 값을 다음 사람들과 비교해나간다. 

더 낮은(즉, 더 좋은 면접 성적) 성적을 가진 사람이 있으면 min_interview에 담는다. 그렇게 되면 특정 지원자의 면접시험 성적과 min_interview만 비교해 특정 지원자의 선발 여부를 결정할 수 있게 된다. 왜냐하면 이미 서류 성적순으로 정렬이 됐기에 지나온 지원자들보다 면접 성적만 낮지 않으면 되기 때문이다.

<내 코드>

sugar = int(input())
result = 0
while sugar != 0:
    if sugar < 0:
        result = -1
        break

    if (sugar % 5) == 0:
        result += (sugar // 5)
        sugar = 0
    else:
        sugar -= 3
        result += 1

print(result)

일단 설탕의 무게가 큰 단위인 5로 나눠지면 몫을 result에 담고 설탕 무게를 0으로 만든다. 만약 5로 나눠지지 않는다면 설탕에서 -3을 해주고 result를 1증가시킨다. 그러다 설탕이 0보다 작아지는 경우에는 5, 3으로 나눌 수 없는 값이기 때문에 -1을 출력하고 반복문을 종료한다.

<내 코드>

N = int(input())

times = [list(map(int, input().split())) for _ in range(N)]
times.sort(key=lambda x: (x[1], x[0])) # 끝 시간으로 정렬 후, 시작 시간으로 정렬

cnt = 1
end_time = times[0][1]
for i in range(1, N):
    if times[i][0] >= end_time: # 앞 요소의 끝 시간보다 현재 요소의 시작시간이 크거나 같을 때
        cnt += 1
        end_time = times[i][1]

print(cnt)

문제에서 제약조건이 다음과 같이 주어졌다.

- 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다.

- 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

최대한 많은 회의를 잡기 위해서는 끝나는 시간이 짧아야 한다. 회의가 빨리 끝나야 다음 회의를 시작할 수 있다. 

그래서 우선 끝나는 시간으로 정렬한다. 여기서 중요한 것이 시작 시간과 끝나는 시간이 같은 케이스다.

예를 들어 (2,2) 와 (1,2) 있을 때 끝나는 시간으로 정렬을 한다면 (2,2)가 먼저 정렬되고 (1,2)가 무시된다. 그래서 시작과 끝 시간이 같은 경우는 시작 시간 기준으로 다시 정렬을 해줘야 한다.