출처: [백준] 2468번 안전 영역

문제

재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 안전한 영역이 최대로 몇 개가 만들어 지는 지를 조사하려고 한다. 이때, 문제를 간단하게 하기 위하여, 장마철에 내리는 비의 양에 따라 일정한 높이 이하의 모든 지점은 물에 잠긴다고 가정한다.

어떤 지역의 높이 정보는 행과 열의 크기가 각각 N인 2차원 배열 형태로 주어지며 배열의 각 원소는 해당 지점의 높이를 표시하는 자연수이다. 예를 들어, 다음은 N=5인 지역의 높이 정보이다.

이제 위와 같은 지역에 많은 비가 내려서 높이가 4 이하인 모든 지점이 물에 잠겼다고 하자. 이 경우에 물에 잠기는 지점을 회색으로 표시하면 다음과 같다.

물에 잠기지 않는 안전한 영역이라 함은 물에 잠기지 않는 지점들이 위, 아래, 오른쪽 혹은 왼쪽으로 인접해 있으며 그 크기가 최대인 영역을 말한다. 위의 경우에서 물에 잠기지 않는 안전한 영역은 5개가 된다(꼭짓점으로만 붙어 있는 두 지점은 인접하지 않는다고 취급한다).

또한 위와 같은 지역에서 높이가 6이하인 지점을 모두 잠기게 만드는 많은 비가 내리면 물에 잠기지 않는 안전한 영역은 아래 그림에서와 같이 네 개가 됨을 확인할 수 있다.

이와 같이 장마철에 내리는 비의 양에 따라서 물에 잠기지 않는 안전한 영역의 개수는 다르게 된다. 위의 예와 같은 지역에서 내리는 비의 양에 따른 모든 경우를 다 조사해 보면 물에 잠기지 않는 안전한 영역의 개수 중에서 최대인 경우는 5임을 알 수 있다.

어떤 지역의 높이 정보가 주어졌을 때, 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 계산하는 프로그램을 작성하시오.

입력

첫째 줄에는 어떤 지역을 나타내는 2차원 배열의 행과 열의 개수를 나타내는 수 N이 입력된다. N은 2 이상 100 이하의 정수이다. 둘째 줄부터 N개의 각 줄에는 2차원 배열의 첫 번째 행부터 N번째 행까지 순서대로 한 행씩 높이 정보가 입력된다. 각 줄에는 각 행의 첫 번째 열부터 N번째 열까지 N개의 높이 정보를 나타내는 자연수가 빈 칸을 사이에 두고 입력된다. 높이는 1이상 100 이하의 정수이다.

출력

첫째 줄에 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 출력한다.

예제 입력 1

1
2
3
4
5
6

5
6 8 2 6 2
3 2 3 4 6
6 7 3 3 2
7 2 5 3 6
8 9 5 2 7

예제 출력 1

1

5

노트

아무 지역도 물에 잠기지 않을 수도 있다.

출처

Olympiad > 한국정보올림피아드 > KOI 2010 > 초등부 2번

• 문제의 오타를 찾은 사람: apjw6112
• 어색한 표현을 찾은 사람: jh05013
• 잘못된 데이터를 찾은 사람: tncks0121

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 브루트포스 알고리즘
• 너비 우선 탐색
• 깊이 우선 탐색

풀이

소스코드_DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

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


def dfs(x, y, h):
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if 0 <= nx < N and 0 <= ny < N and ground[nx][ny] > h and not visited[nx][ny]:
            visited[nx][ny] = True
            dfs(nx, ny, h)


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

result = 0
for k in range(max(max(ground))):
    count = 0
    visited = [[False] * N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if ground[i][j] > k and not visited[i][j]:
                count += 1
                visited[i][j] = True
                dfs(i, j, k)
    result = max(result, count)
print(result)

출처: [백준] 4963번 섬의개수

문제

정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오.

한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다.

두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다.

둘째 줄부터 h개 줄에는 지도가 주어진다. 1은 땅, 0은 바다이다.

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

출력

각 테스트 케이스에 대해서, 섬의 개수를 출력한다.

예제 입력 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

1 1
0
2 2
0 1
1 0
3 2
1 1 1
1 1 1
5 4
1 0 1 0 0
1 0 0 0 0
1 0 1 0 1
1 0 0 1 0
5 4
1 1 1 0 1
1 0 1 0 1
1 0 1 0 1
1 0 1 1 1
5 5
1 0 1 0 1
0 0 0 0 0
1 0 1 0 1
0 0 0 0 0
1 0 1 0 1
0 0

예제 출력 1

1
2
3
4
5
6

0
1
1
3
1
9

출처

ICPC > Regionals > Asia Pacific > Japan > Japan Domestic Contest > 2009 Japan Domestic Contest B번

• 문제를 번역한 사람: baekjoon
• 문제의 오타를 찾은 사람: j4bez

링크

• TJU Online Judge

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 깊이 우선 탐색

풀이

소스코드_DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

# 방향정의 (상,하,좌,우, 1,5,7,9)
dx = [-1, 1, 0, 0, -1, 1, 1, -1]
dy = [0, 0, -1, 1, 1, 1, -1, -1]


def dfs(x, y):
    ground[x][y] = -1

    for i in range(8):
        nx = x + dx[i]
        ny = y + dy[i]

        if 0 <= nx < H and 0 <= ny < W and ground[nx][ny] == 1:
            dfs(nx, ny)


while True:
    W, H = map(int, input().split())
    if W == 0 and H == 0:
        break

    ground = [list(map(int, input().split())) for _ in range(H)]

    count = 0
    for i in range(H):
        for j in range(W):
            if ground[i][j] == 1:
                dfs(i, j)
                count += 1
    print(count)

1. “개인정보 관리 우려”…日정부, 네이버 자회사 라인 ‘릴레이 조사’

“개인정보 관리 우려”…日정부, 네이버 자회사 라인 릴레이 조사 - 매일경제 (mk.co.kr)

네이버 자회사 라인이 개인정보 관리에 문제가 있다는 논란이 일면서 일본 정부의 조사를 받고 있어, 일본 최대 포털업체 야후재팬과 합작회사를 출범시키며 핵심 사업 중 하나로 내세운 공공사업(B2G)에 타격이 불가피할 것이란 관측이 적지 않다.

일본 정부도 라인 플랫폼을 활용해 행정 서비스의 디지털 전환을 의욕적으로 추진해왔는데 행정 처분 등이 결정될 때까지 올스톱이 불가피하며, 당장 라인을 대체할 플랫폼을 찾기도 쉽지 않아 고민에 빠졌다.

2. 빅블러 시대…네이버·토스 등 ‘적’과 동맹 잇는 은행들

빅블러 시대…네이버·토스 등 ‘적’과 동맹 잇는 은행들 (ekn.kr)

은행들이 마이데이터 시대(본인신용정보관리업)를 앞두고 기존에 가지고 있던 금융 데이터만을 활용하기에 한계가 있어, 이종산업과 협업을 맺고 축적하는 데이터 범위를 확대하겠다는 의도로 네이버, 토스 등 빅테크(대형 IT기업)·핀테크 기업과 손을 잡으며 적과의 동맹을 이어가고 있다.

산업 간 경계가 사라지는 빅블러 시대인 만큼 금융과 이종산업 간 결합 사례는 더욱 많아질 것으로 보이며, 특히 대부분의 기업이 공통적으로 ‘디지털 플랫폼 기업’을 지향하고 있어, 다양한 분야를 아우르는 데이터를 가지는 것은 곧 경쟁력으로 여겨진다.

3. [IT큐레이션] 네이버는 지금 콘텐츠 앱 생태계를 만들고 있다

[IT큐레이션] 네이버는 지금 콘텐츠 앱 생태계를 만들고 있다 < IT/스타트업 < IT/게임 < 기사본문 - 이코노믹리뷰 (econovill.com)

네이버의 콘텐츠 확보 전략은 단순히 좋은 콘텐츠 IP를 확보해 이를 바탕으로 양질의 플랫폼 서비스를 하겠다는 일차원적 접근이 아니라 존재하는 모든 온라인과 오프라인의 활동을 콘텐츠로 인식해 말 그대로 콘텐츠 토털 생태계를 구축하고 있다. 실제로 대리운전, 게임, 메모, 미팅, 협업툴 등 세상 만물이 모두 콘텐츠가 되어 막강한 플랫폼으로 달려왔으며 구글과 애플은 이들에게 수익을 제공해 방대한 생태계를 만들어냈다.

4. 상장 채비 서두르는 카카오페이…발목 잡는 ‘차이나 리스크’ 해소될까

상장 채비 서두르는 카카오페이…발목 잡는 ‘차이나 리스크’ 해소될까 : 네이버 뉴스 (naver.com)

카카오페이는 2대주주 중국 앤트그룹의 적격성 문제에 발목 잡혀 신산업으로 주목받고 있는 마이데이터 사업 관련 일부 서비스를 중단하는 등 ‘차이나 리스크’로 사업에 차질을 빚어왔다.

그러나 최근 금융당국 내에서 카카오페이의 마이데이터 적격성 심사와 관련해 기류변화가 나타나고 있어서 최대 걸림돌이 사라질 것이라는 분위기가 지배적이고, 그동안 금융당국은 고유의 최종 결정권한을 사실상 해외 금융당국에게 맡기는 것과 다름 없다는 비난을 받아왔는데, 이같은 분위기가 반전되기 시작한 것이다.

5. “역대 최강 스펙, 성능 자신있다”…애플 신제품들 어떻길래 [종합]

[“역대 최강 스펙, 성능 자신있다”…애플 신제품들 어떻길래 종합] : 네이버 뉴스 (naver.com)

애플은 21일 오전 2시(한국시간) 미국 캘리포니아주 쿠퍼티노 애플파크 스티브잡스 극장에서 신제품 공개행사를 온라인으로 열고 태블릿 PC ‘아이패드 프로’, 일체형 데스크톱 ‘아이맥’, 무선 위치추적 장치 ‘에어태그’ 등 신제품을 다수 선보였다.

애플은 2023년까지 제조 공급망 및 제품에서 발생하는 탄소 배출량의 75%를 감축하는 한편 재활용 소재를 제품 생산에 적극 활용할 계획으로 팀쿡 애플 최고경영자(CEO)는 “매년 탄소 배출량을 100만 톤씩 줄이겠다”는 목표를 밝혔다.

6. 생각만으로 컴퓨터 사용? 성큼 다가온 미래, BCI

생각만으로 컴퓨터 사용? 성큼 다가온 미래, BCI : 네이버 뉴스 (naver.com)

테슬라 CEO 일론 머스크가 설립한 스타트업 ‘뉴럴링크’는 . 뇌에 칩을 이식한 원숭이가 생각만으로 간단한 게임을 즐기는 모습이 담긴 영상을 지난 9일 유튜브에 공개했다

지금까지 BCI가 가장 널리 연구되고 활용됐던 영역은 의료분야로 뇌 질환 예방 또는 치료하는 용도로 쓰거나 신경손상 환자 재활에 활용할 수 있으며, 가령 손상된 뇌 기능 일부를 대신하는 칩을 이식해 뇌 질환을 치료한다거나, 팔다리가 마비된 사람이 생각만으로 컴퓨터나 휠체어를 조작하는 게 가능하다.

• BCI: 뇌-컴퓨터 인터페이스(BCI, Brain Computer Interface): 뇌와 컴퓨터가 직접 상호작용할 수 있게 하는 인터페이스

출처: [백준] 11724번 연결 요소의 개수

문제

방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.

출력

첫째 줄에 연결 요소의 개수를 출력한다.

예제 입력 1

1
2
3
4
5
6

6 5
1 2
2 5
5 1
3 4
4 6

예제 출력 1

1

2

예제 입력 2

1
2
3
4
5
6
7
8
9

6 8
1 2
2 5
5 1
3 4
4 6
5 4
2 4
2 3

예제 출력 2

1

1

힌트

출처

• 문제를 만든 사람: baekjoon
• 데이터를 추가한 사람: djm03178, YunGoon
• 잘못된 조건을 찾은 사람: songjuh

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 깊이 우선 탐색

풀이

소스코드_DFS(List1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline


def dfs(graph, v, visited):
    visited[v] = True
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)


N, M = map(int, input().split())
graph = [[] for _ in range(N + 1)]
visited = [False] * (N + 1)
component = 0

for _ in range(M):
    src, dest = map(int, input().split())
    graph[src].append(dest)
    graph[dest].append(src)

for i in range(1, N + 1):
    if not visited[i]:
        dfs(graph, i, visited)
        component += 1

print(component)

소스코드_DFS(List2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline


def dfs(graph, v, visited):
    visited[v] = True
    for i in range(1, N + 1):
        if not visited[i] and graph[v][i] == 1:
            dfs(graph, i, visited)


N, M = map(int, input().split())
graph = [[0] * (N + 1) for _ in range(N + 1)]
for _ in range(M):
    x, y = map(int, input().split())
    graph[x][y] = 1
    graph[y][x] = 1

visited = [False] * (N + 1)
component = 0

for i in range(1, N + 1):
    if not visited[i]:
        dfs(graph, i, visited)
        component += 1
print(component)

소스코드_DFS(Dict)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline


def dfs(graph, v, visited):
    visited[v] = True
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)


N, M = map(int, input().split())
graph = {}
for i in range(N + 1):
    graph[i] = set()

for _ in range(M):
    u, v = map(int, input().split())
    graph[u].add(v)
    graph[v].add(u)

visited = [False] * (N + 1)
component = 0

for i in range(1, N + 1):
    if not visited[i]:
        dfs(graph, i, visited)
        component += 1

print(component)

출처: [백준] 2667번 단지번호붙이기

문제

<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. <그림 2>는 <그림 1>을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.

입력

첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고, 그 다음 N줄에는 각각 N개의 자료(0혹은 1)가 입력된다.

출력

첫 번째 줄에는 총 단지수를 출력하시오. 그리고 각 단지내 집의 수를 오름차순으로 정렬하여 한 줄에 하나씩 출력하시오.

예제 입력 1

1
2
3
4
5
6
7
8

7
0110100
0110101
1110101
0000111
0100000
0111110
0111000

예제 출력 1

1
2
3
4

3
7
8
9

힌트

출처

• Olympiad > 한국정보올림피아드 > KOI 1996 > 초등부 1번
  • 잘못된 데이터를 찾은 사람: djm03178
  • 데이터를 추가한 사람: djm03178, jh05013
  • 문제의 오타를 찾은 사람: metadata

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 깊이 우선 탐색

풀이

소스코드_DFS(List)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

# 방향 정의(상,하,좌,우)
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]


def dfs(x, y, house):
    ground[x][y] = 0  # 해당 지점은 확인
    
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if 0 <= nx < N and 0 <= ny < N:
            if ground[nx][ny] == 1:
                house = dfs(nx, ny, house + 1)
    return house


N = int(input())
ground = [list(map(int, input().rstrip())) for _ in range(N)]
houses = []  # 각 단지내 집의 수

for i in range(N):
    for j in range(N):
        if ground[i][j] == 1:
            houses.append(dfs(i, j, 1))

print(len(houses))
for house in sorted(houses):
    print(house)

출처: [백준] 1012번 유기농 배추

문제

차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다.

(한 배추의 상하좌우 네 방향에 다른 배추가 위치한 경우에 서로 인접해있다고 간주한다)

한나가 배추를 재배하는 땅은 고르지 못해서 배추를 군데군데 심어놓았다. 배추들이 모여있는 곳에는 배추흰지렁이가 한 마리만 있으면 되므로 서로 인접해있는 배추들이 몇 군데에 퍼져있는지 조사하면 총 몇 마리의 지렁이가 필요한지 알 수 있다.

예를 들어 배추밭이 아래와 같이 구성되어 있으면 최소 5마리의 배추흰지렁이가 필요하다.

(0은 배추가 심어져 있지 않은 땅이고, 1은 배추가 심어져 있는 땅을 나타낸다.)

입력

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 첫째 줄에는 배추를 심은 배추밭의 가로길이 M(1 ≤ M ≤ 50)과 세로길이 N(1 ≤ N ≤ 50), 그리고 배추가 심어져 있는 위치의 개수 K(1 ≤ K ≤ 2500)이 주어진다. 그 다음 K줄에는 배추의 위치 X(0 ≤ X ≤ M-1), Y(0 ≤ Y ≤ N-1)가 주어진다.

출력

각 테스트 케이스에 대해 필요한 최소의 배추흰지렁이 마리 수를 출력한다.

예제 입력 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

2
10 8 17
0 0
1 0
1 1
4 2
4 3
4 5
2 4
3 4
7 4
8 4
9 4
7 5
8 5
9 5
7 6
8 6
9 6
10 10 1
5 5

예제 출력 1

1
2

5
1

예제 입력 2

1
2
3
4
5
6
7
8

1
5 3 6
0 2
1 2
2 2
3 2
4 2
4 0

예제 출력 2

1

2

힌트

출처

• 문제를 만든 사람: author2
• 빠진 조건을 찾은 사람: jinsj1

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 깊이 우선 탐색

풀이

소스코드_DFS(List)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

# 이동할 네 방향 정의 (상, 하, 좌, 우)
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]


def dfs(x, y):
    ground[x][y] = 0 # 해당 지점은 확인

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if nx < 0 or ny < 0 or nx >= N or ny >= M:
            continue
        else:
            if ground[nx][ny] == 1:
                dfs(nx, ny)


T = int(input())
for _ in range(T):
    M, N, K = map(int, input().split())
    ground = [[0 for _ in range(M)] for _ in range(N)]
    count = 0
    for _ in range(K):
        X, Y = map(int, input().split())
        ground[Y][X] = 1

    for i in range(N):
        for j in range(M):
            if ground[i][j] == 1:
                dfs(i, j)
                count += 1
    print(count)

출처: [백준] 2455번 지능형 기차

문제

최근에 개발된 지능형 기차가 1번역(출발역)부터 4번역(종착역)까지 4개의 정차역이 있는 노선에서 운행되고 있다. 이 기차에는 타거나 내리는 사람 수를 자동으로 인식할 수 있는 장치가 있다. 이 장치를 이용하여 출발역에서 종착역까지 가는 도중 기차 안에 사람이 가장 많을 때의 사람 수를 계산하려고 한다. 단, 이 기차를 이용하는 사람들은 질서 의식이 투철하여, 역에서 기차에 탈 때, 내릴 사람이 모두 내린 후에 기차에 탄다고 가정한다.

예를 들어, 위와 같은 경우를 살펴보자. 이 경우, 기차 안에 사람이 가장 많은 때는 2번역에서 3명의 사람이 기차에서 내리고, 13명의 사람이 기차에 탔을 때로, 총 42명의 사람이 기차 안에 있다.

이 기차는 다음 조건을 만족하면서 운행된다고 가정한다.

1. 기차는 역 번호 순서대로 운행한다.
2. 출발역에서 내린 사람 수와 종착역에서 탄 사람 수는 0이다.
3. 각 역에서 현재 기차에 있는 사람보다 더 많은 사람이 내리는 경우는 없다.
4. 기차의 정원은 최대 10,000명이고, 정원을 초과하여 타는 경우는 없다.

4개의 역에 대해 기차에서 내린 사람 수와 탄 사람 수가 주어졌을 때, 기차에 사람이 가장 많을 때의 사람 수를 계산하는 프로그램을 작성하시오.

입력

각 역에서 내린 사람 수와 탄 사람 수가 빈칸을 사이에 두고 첫째 줄부터 넷째 줄까지 역 순서대로 한 줄에 하나씩 주어진다.

출력

첫째 줄에 최대 사람 수를 출력한다.

예제 입력 1

1
2
3
4

0 32
3 13
28 25
39 0

예제 출력 1

1

42

힌트

출처

Olympiad > 한국정보올림피아드 > 한국정보올림피아드시․도지역본선 > 지역본선 2011 > 초등부 1번

• 데이터를 추가한 사람: ryu_eclipse, surung9898

알고리즘 분류

• 수학
• 구현
• 사칙연산

시간 제한

풀이

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14

import sys

input = sys.stdin.readline

max_p = 0
sum_p = 0
for _ in range(4):
    out_p, in_p = map(int, input().split())
    sum_p -= out_p
    sum_p += in_p
    max_p = max(max_p, sum_p)

print(max_p)

출처: [백준] 2490번 윷놀이

문제

우리나라 고유의 윷놀이는 네 개의 윷짝을 던져서 배(0)와 등(1)이 나오는 숫자를 세어 도, 개, 걸, 윷, 모를 결정한다. 네 개 윷짝을 던져서 나온 각 윷짝의 배 혹은 등 정보가 주어질 때 도(배 한 개, 등 세 개), 개(배 두 개, 등 두 개), 걸(배 세 개, 등 한 개), 윷(배 네 개), 모(등 네 개) 중 어떤 것인지를 결정하는 프로그램을 작성하라.

입력

첫째 줄부터 셋째 줄까지 각 줄에 각각 한 번 던진 윷짝들의 상태를 나타내는 네 개의 정수(0 또는 1)가 빈칸을 사이에 두고 주어진다.

출력

첫째 줄부터 셋째 줄까지 한 줄에 하나씩 결과를 도는 A, 개는 B, 걸은 C, 윷은 D, 모는 E로 출력한다.

예제 입력 1

1
2
3

0 1 0 1
1 1 1 0
0 0 1 1

예제 출력 1

1
2
3

B
A
B

힌트

출처

Olympiad > 한국정보올림피아드 > 한국정보올림피아드시․도지역본선 > 지역본선 2009 > 초등부 1번

• 잘못된 데이터를 찾은 사람: djm03178
• 문제의 오타를 찾은 사람: eric00513

알고리즘 분류

• 구현

시간 제한

풀이

소스코드 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

import sys

input = sys.stdin.readline

for _ in range(3):
    lists = list(map(int, input().split()))

    if lists.count(1) == 0:
        print('D')
    elif lists.count(1) == 1:
        print('C')
    elif lists.count(1) == 2:
        print('B')
    elif lists.count(1) == 3:
        print('A')
    elif lists.count(1) == 4:
        print('E')

소스코드 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

import sys

input = sys.stdin.readline

# 0: 배
# 1: 등

# 도(0,111), 개(00,11), 걸(000,1), 윷(0000), 모(1111)

for _ in range(3):
    lists = list(map(int, input().split()))

    front = 0  # 배
    rear = 0  # 등

    for num in lists:
        if num == 0:
            front += 1
        else:
            rear += 1

    if rear == 0 and front == 4:
        print('D')
    elif rear == 1 and front == 3:
        print('C')
    elif rear == 2 and front == 2:
        print('B')
    elif rear == 3 and front == 1:
        print('A')
    elif rear == 4 and front == 0:
        print('E')

출처: [백준] 1476번 날짜 계산

문제

준규가 사는 나라는 우리가 사용하는 연도와 다른 방식을 이용한다. 준규가 사는 나라에서는 수 3개를 이용해서 연도를 나타낸다. 각각의 수는 지구, 태양, 그리고 달을 나타낸다.

지구를 나타내는 수를 E, 태양을 나타내는 수를 S, 달을 나타내는 수를 M이라고 했을 때, 이 세 수는 서로 다른 범위를 가진다. (1 ≤ E ≤ 15, 1 ≤ S ≤ 28, 1 ≤ M ≤ 19)

우리가 알고있는 1년은 준규가 살고있는 나라에서는 1 1 1로 나타낼 수 있다. 1년이 지날 때마다, 세 수는 모두 1씩 증가한다. 만약, 어떤 수가 범위를 넘어가는 경우에는 1이 된다.

예를 들어, 15년은 15 15 15로 나타낼 수 있다. 하지만, 1년이 지나서 16년이 되면 16 16 16이 아니라 1 16 16이 된다. 이유는 1 ≤ E ≤ 15 라서 범위를 넘어가기 때문이다.

E, S, M이 주어졌고, 1년이 준규가 사는 나라에서 1 1 1일때, 준규가 사는 나라에서 E S M이 우리가 알고 있는 연도로 몇 년인지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 세 수 E, S, M이 주어진다. 문제에 나와있는 범위를 지키는 입력만 주어진다.

출력

첫째 줄에 E S M으로 표시되는 가장 빠른 연도를 출력한다. 1 1 1은 항상 1이기 때문에, 정답이 음수가 나오는 경우는 없다.

예제 입력 1

1

1 16 16

예제 출력 1

1

16

예제 입력 2

1

1 1 1

예제 출력 2

1

1

예제 입력 3

1

1 2 3

예제 출력 3

1

5266

예제 입력 4

1

15 28 19

예제 출력 4

1

7980

힌트

출처

• 문제를 번역한 사람: baekjoon
• 문제의 오타를 찾은 사람: imgosari, yehyuns://www.acmicpc.net/user/surung9898)

알고리즘 분류

• 수학
• 구현
• 정수론
• 중국인의 나머지 정리

시간 제한

풀이

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14

import sys

input = sys.stdin.readline

E, S, M = map(int, input().split())

year = 1

while True:
    if (year - E) % 15 == 0 and (year - S) % 28 == 0 and (year - M) % 19 == 0:
        print(year)
        break
    year += 1

출처: [백준] 2475번 검증수

문제

컴퓨터를 제조하는 회사인 KOI 전자에서는 제조하는 컴퓨터마다 6자리의 고유번호를 매긴다. 고유번호의 처음 5자리에는 00000부터 99999까지의 수 중 하나가 주어지며 6번째 자리에는 검증수가 들어간다. 검증수는 고유번호의 처음 5자리에 들어가는 5개의 숫자를 각각 제곱한 수의 합을 10으로 나눈 나머지이다.

예를 들어 고유번호의 처음 5자리의 숫자들이 04256이면, 각 숫자를 제곱한 수들의 합 0+16+4+25+36 = 81 을 10으로 나눈 나머지인 1이 검증수이다.

입력

첫째 줄에 고유번호의 처음 5자리의 숫자들이 빈칸을 사이에 두고 하나씩 주어진다.

출력

첫째 줄에 검증수를 출력한다.

예제 입력 1

1

0 4 2 5 6

예제 출력 1

1

1

힌트

출처

Olympiad > 한국정보올림피아드 > 한국정보올림피아드시․도지역본선 > 지역본선 2010 > 초등부 1번

• 잘못된 데이터를 찾은 사람: rory143, tncks0121

알고리즘 분류

• 수학
• 구현
• 사칙연산

시간 제한

풀이

소스코드

1
2
3
4
5
6
7
8
9
10
11
12

import sys

input = sys.stdin.readline

lists = list(map(int, input().split()))

result = 0
for num in lists:
    result += num ** 2

print(result % 10)