출처: [백준] 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)

출처: [백준] 9466번 텀 프로젝트

문제

이번 가을학기에 ‘문제 해결’ 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 수도 있다. 프로젝트 팀을 구성하기 위해, 모든 학생들은 프로젝트를 함께하고 싶은 학생을 선택해야 한다. (단, 단 한 명만 선택할 수 있다.) 혼자 하고 싶어하는 학생은 자기 자신을 선택하는 것도 가능하다.

학생들이(s1, s2, …, sr)이라 할 때, r=1이고 s1이 s1을 선택하는 경우나, s1이 s2를 선택하고, s2가 s3를 선택하고,…, sr-1이 sr을 선택하고, sr이 s1을 선택하는 경우에만 한 팀이 될 수 있다.

예를 들어, 한 반에 7명의 학생이 있다고 하자. 학생들을 1번부터 7번으로 표현할 때, 선택의 결과는 다음과 같다.

위의 결과를 통해 (3)과 (4, 7, 6)이 팀을 이룰 수 있다. 1, 2, 5는 어느 팀에도 속하지 않는다.

주어진 선택의 결과를 보고 어느 프로젝트 팀에도 속하지 않는 학생들의 수를 계산하는 프로그램을 작성하라.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫 줄에는 학생의 수가 정수 n (2 ≤ n ≤ 100,000)으로 주어진다. 각 테스트 케이스의 둘째 줄에는 선택된 학생들의 번호가 주어진다. (모든 학생들은 1부터 n까지 번호가 부여된다.)

출력

각 테스트 케이스마다 한 줄에 출력하고, 각 줄에는 프로젝트 팀에 속하지 못한 학생들의 수를 나타내면 된다.

예제 입력 1

1
2
3
4
5

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

예제 출력 1

1
2

3
0

힌트

출처

• ICPC > Regionals > Asia Pacific > Korea > Asia Regional - Daejeon 2013 L번
  • 문제를 번역한 사람: plzrun
  • 데이터를 추가한 사람: qwe123rt45

링크

• ACM-ICPC Live Archive

알고리즘 분류

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

풀이

• 연결 된 점이 싸이클이 되면 팀 형성…

소스코드

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

test_case = int(input())


def dfs(v):
    global result
    team[v] = True
    cycle.append(v)
    num = arr[v]

    if not team[num]:
        dfs(num)
    else:
        if num in cycle:
            result += cycle[cycle.index(num):]
        return


for _ in range(test_case):
    N = int(input())
    arr = [0] + list(map(int, input().split()))
    team = [True] + [False] * N
    result = []

    for i in range(1, N + 1):
        if not team[i]:
            cycle = []
            dfs(i)
    print(N - len(result))

출처: [백준] 10991번 별 찍기 - 16

문제

예제를 보고 규칙을 유추한 뒤에 별을 찍어 보세요.

입력

첫째 줄에 N(1 ≤ N ≤ 100)이 주어진다.

출력

첫째 줄부터 N번째 줄까지 차례대로 별을 출력한다.

예제 입력 1

1

1

예제 출력 1

1

*

예제 입력 2

1

2

예제 출력 2

1
2

 *
* *

예제 입력 3

1

3

예제 출력 3

1
2
3

  *
 * *
* * *

예제 입력 4

1

4

예제 출력 4

1
2
3
4

   *
  * *
 * * *
* * * *

힌트

출처

• 문제를 만든 사람: baekjoon
• 문제의 오타를 찾은 사람: eric00513, moonhi123

알고리즘 분류

• 구현

시간 제한

풀이

소스코드

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

import sys

input = sys.stdin.readline

N = int(input())

for i in range(1, N + 1):
    print(' ' * (N - i), end='')
    for j in range(i):
        print('*', end=' ')
    print()

출처: [백준] 2523번 별 찍기 - 13

문제

예제를 보고 규칙을 유추한 뒤에 별을 찍어 보세요.

입력

첫째 줄에 N(1 ≤ N ≤ 100)이 주어진다.

출력

첫째 줄부터 2×N-1번째 줄까지 차례대로 별을 출력한다.

예제 입력 1

1

3

예제 출력 1

1
2
3
4
5

*
**
***
**
*

힌트

출처

• 문제를 만든 사람: baekjoon

알고리즘 분류

• 구현

시간 제한

풀이

소스코드

1
2
3
4
5
6
7
8
9
10
11

import sys

input = sys.stdin.readline

N = int(input())

for i in range(1, N + 1):
    print('*' * i)
for i in reversed(range(1, N)):
    print('*' * i)

출처: [백준] 2522번 별 찍기 - 12

문제

예제를 보고 규칙을 유추한 뒤에 별을 찍어 보세요.

입력

첫째 줄에 N(1 ≤ N ≤ 100)이 주어진다.

출력

첫째 줄부터 2×N-1번째 줄까지 차례대로 별을 출력한다.

예제 입력 1

1

3

예제 출력 1

1
2
3
4
5

  *
 **
***
 **
  *

힌트

출처

• 문제를 만든 사람: baekjoon

알고리즘 분류

• 구현

시간 제한

풀이

소스코드

1
2
3
4
5
6
7
8
9
10
11

import sys

input = sys.stdin.readline

N = int(input())

for i in range(1, N + 1):
    print(' ' * (N - i) + '*' * i)
for i in reversed(range(1, N)):
    print(' ' * (N - i) + '*' * i)

출처: [백준] 2446번 별 찍기 - 9

문제

예제를 보고 규칙을 유추한 뒤에 별을 찍어 보세요.

입력

첫째 줄에 N(1 ≤ N ≤ 100)이 주어진다.

출력

첫째 줄부터 2×N-1번째 줄까지 차례대로 별을 출력한다.

예제 입력 1

1

5

예제 출력 1

1
2
3
4
5
6
7
8
9

*********
 *******
  *****
   ***
    *
   ***
  *****
 *******
*********

힌트

출처

• 문제를 만든 사람: baekjoon

알고리즘 분류

• 구현

시간 제한

풀이

소스코드

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

import sys

input = sys.stdin.readline

N = int(input())

for i in reversed(range(1, N + 1)):
    print(' ' * (N - i) + "*" * (2 * i - 1))

for i in range(2, N + 1):
    print(' ' * (N - i) + "*" * (2 * i - 1))

출처: [백준] 2444번 별 찍기 - 7

문제

예제를 보고 규칙을 유추한 뒤에 별을 찍어 보세요.

입력

첫째 줄에 N(1 ≤ N ≤ 100)이 주어진다.

출력

첫째 줄부터 2×N-1번째 줄까지 차례대로 별을 출력한다.

예제 입력 1

1

5

예제 출력 1

1
2
3
4
5
6
7
8
9

    *
   ***
  *****
 *******
*********
 *******
  *****
   ***
    *

힌트

출처

• 문제를 만든 사람: baekjoon

알고리즘 분류

• 구현

시간 제한

풀이

소스코드

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

import sys

input = sys.stdin.readline

N = int(input())

for i in range(1, N + 1):
    print(' ' * (N - i) + '*' * (2 * i - 1))

for i in reversed(range(1, N)):
    print(' ' * (N - i) + '*' * (2 * i - 1))