출처: [백준] 10972번 다음 순열

문제

1부터 N까지의 수로 이루어진 순열이 있다. 이때, 사전순으로 다음에 오는 순열을 구하는 프로그램을 작성하시오.

사전 순으로 가장 앞서는 순열은 오름차순으로 이루어진 순열이고, 가장 마지막에 오는 순열은 내림차순으로 이루어진 순열이다.

N = 3인 경우에 사전순으로 순열을 나열하면 다음과 같다.

• 1, 2, 3
• 1, 3, 2
• 2, 1, 3
• 2, 3, 1
• 3, 1, 2
• 3, 2, 1

입력

첫째 줄에 N(1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄에 순열이 주어진다.

출력

첫째 줄에 입력으로 주어진 순열의 다음에 오는 순열을 출력한다. 만약, 사전순으로 마지막에 오는 순열인 경우에는 -1을 출력한다.

예제 입력 1

1
2

4
1 2 3 4

예제 출력 1

1

1 2 4 3

예제 입력 2

1
2

5
5 4 3 2 1

예제 출력 2

1

-1

출처

• 문제를 만든 사람: baekjoon

알고리즘 분류

• 수학
• 조합론

소스코드

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

import sys

input = sys.stdin.readline

N = int(input())
compare_list = list(map(int, input().split()))


i, j, k = [len(compare_list) - 1 for _ in range(3)]  # 맨 뒤부터...
while i > 0 and compare_list[i - 1] >= compare_list[i]:  # 맨 뒤부터 오름차순... 즉 내림차순일 경우
    i -= 1

if not i:  # 다음 순열이 없을 경우
    print(-1)
    exit(0)

while compare_list[i - 1] >= compare_list[j]:
    j -= 1
compare_list[i - 1], compare_list[j] = compare_list[j], compare_list[i - 1]

while i < k:
    compare_list[i], compare_list[k] = compare_list[k], compare_list[i]
    i += 1
    k -= 1

print(*compare_list)

출처: [백준] 1292번 쉽게 푸는 문제

문제

동호는 내년에 초등학교를 입학한다. 그래서 동호 어머니는 수학 선행 학습을 위해 쉽게 푸는 문제를 동호에게 주었다.

이 문제는 다음과 같다. 1을 한 번, 2를 두 번, 3을 세 번, 이런 식으로 1 2 2 3 3 3 4 4 4 4 5 .. 이러한 수열을 만들고 어느 일정한 구간을 주면 그 구간의 합을 구하는 것이다.

하지만 동호는 현재 더 어려운 문제를 푸느라 바쁘기에 우리가 동호를 도와주자.

입력

첫째 줄에 구간의 시작과 끝을 나타내는 정수 A, B(1 ≤ A ≤ B ≤ 1,000)가 주어진다. 즉, 수열에서 A번째 숫자부터 B번째 숫자까지 합을 구하면 된다.

출력

첫 줄에 구간에 속하는 숫자의 합을 출력한다.

예제 입력 1

1

3 7

예제 출력 1

1

15

출처

• 문제를 만든 사람: author6

알고리즘 분류

• 수학
• 구현

소스코드

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

import sys

input = sys.stdin.readline

A, B = map(int, input().split())

cur_value = 1
position = 1
result = 0

for i in range(A, B + 1):
    while position < i:
        cur_value += 1
        position += cur_value
    result += cur_value

print(result)

출처: [백준] 1748번 수 이어 쓰기 1

문제

1부터 N까지의 수를 이어서 쓰면 다음과 같이 새로운 하나의 수를 얻을 수 있다.

1234567891011121314151617181920212223…

이렇게 만들어진 새로운 수는 몇 자리 수일까? 이 수의 자릿수를 구하는 프로그램을 작성하시오.

입력

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

출력

첫째 줄에 새로운 수의 자릿수를 출력한다.

예제 입력 1

1

5

예제 출력 1

1

5

예제 입력 2

1

15

예제 출력 2

1

21

예제 입력 3

1

120

예제 출력 3

1

252

출처

• Olympiad > Croatian Highschool Competitions in Informatics > 2004 > Regional Competition - Juniors 1번
  • 문제를 번역한 사람: author5

알고리즘 분류

• 수학
• 구현

소스코드

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

N = input()
exp = 0
result = 0
while exp < len(N) - 1:
    result += 9 * (10 ** exp) * (exp + 1)
    exp += 1
result += (int(N) - (10 ** (len(N) - 1)) + 1) * len(N)
print(result)


---------------
# 시간초과
N = int(input())
new_num = ""
for i in range(1, N + 1):
    new_num += str(i)

print(len(new_num))

출처: [백준] 11723번 집합

문제

비어있는 공집합 S가 주어졌을 때, 아래 연산을 수행하는 프로그램을 작성하시오.

• add x: S에 x를 추가한다. (1 ≤ x ≤ 20) S에 x가 이미 있는 경우에는 연산을 무시한다.
• remove x: S에서 x를 제거한다. (1 ≤ x ≤ 20) S에 x가 없는 경우에는 연산을 무시한다.
• check x: S에 x가 있으면 1을, 없으면 0을 출력한다. (1 ≤ x ≤ 20)
• toggle x: S에 x가 있으면 x를 제거하고, 없으면 x를 추가한다. (1 ≤ x ≤ 20)
• all: S를 {1, 2, …, 20} 으로 바꾼다.
• empty: S를 공집합으로 바꾼다.

입력

첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다.

둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다.

출력

check 연산이 주어질때마다, 결과를 출력한다.

예제 입력 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
26
27

26
add 1
add 2
check 1
check 2
check 3
remove 2
check 1
check 2
toggle 3
check 1
check 2
check 3
check 4
all
check 10
check 20
toggle 10
remove 20
check 10
check 20
empty
check 1
toggle 1
check 1
toggle 1
check 1

예제 출력 1

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

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

출처

• 문제를 만든 사람: baekjoon
• 빠진 조건을 찾은 사람: djm03178
• 데이터를 추가한 사람: houma757
• 문제의 오타를 찾은 사람: pichulias://www.acmicpc.net/user/djm03178)

알고리즘 분류

• 구현
• 비트마스킹

소스코드

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

input = sys.stdin.readline

M = int(input())
S = set()

for _ in range(M):
    comm = input().strip().split()

    if comm[0] == 'add':
        S.add(int(comm[1]))
    elif comm[0] == 'remove':
        S.discard(int(comm[1]))
    elif comm[0] == 'check':
        if int(comm[1]) in S:
            print(1)
        else:
            print(0)
    elif comm[0] == 'toggle':
        if int(comm[1]) in S:
            S.discard(int(comm[1]))
        else:
            S.add(int(comm[1]))
    elif comm[0] == 'all':
        S = set([i for i in range(1, 21)])
    elif comm[0] == 'empty':
        S = set()

출처: [백준] 2504번 괄호의 값

문제

4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다.

1. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다.
2. 만일 X가 올바른 괄호열이면 ‘(X)’이나 ‘[X]’도 모두 올바른 괄호열이 된다.
3. X와 Y 모두 올바른 괄호열이라면 이들을 결합한 XY도 올바른 괄호열이 된다.

예를 들어 ‘(()[[]])’나 ‘(())[][]’ 는 올바른 괄호열이지만 ‘([)]’ 나 ‘(()()[]’ 은 모두 올바른 괄호열이 아니다. 우리는 어떤 올바른 괄호열 X에 대하여 그 괄호열의 값(괄호값)을 아래와 같이 정의하고 값(X)로 표시한다.

1. ‘()’ 인 괄호열의 값은 2이다.
2. ‘[]’ 인 괄호열의 값은 3이다.
3. ‘(X)’ 의 괄호값은 2×값(X) 으로 계산된다.
4. ‘[X]’ 의 괄호값은 3×값(X) 으로 계산된다.
5. 올바른 괄호열 X와 Y가 결합된 XY의 괄호값은 값(XY)= 값(X)+값(Y) 로 계산된다.

예를 들어 ‘(()[[]])([])’ 의 괄호값을 구해보자. ‘()[[]]’ 의 괄호값이 2 + 3×3=11 이므로 ‘(()[[ ]])’의 괄호값은 2×11=22 이다. 그리고 ‘([])’의 값은 2×3=6 이므로 전체 괄호열의 값은 22 + 6 = 28 이다.

여러분이 풀어야 할 문제는 주어진 괄호열을 읽고 그 괄호값을 앞에서 정의한대로 계산하여 출력하는 것이다.

입력

첫째 줄에 괄호열을 나타내는 문자열(스트링)이 주어진다. 단 그 길이는 1 이상, 30 이하이다.

출력

첫째 줄에 그 괄호열의 값을 나타내는 정수를 출력한다. 만일 입력이 올바르지 못한 괄호열이면 반드시 0을 출력해야 한다.

예제 입력 1

1

(()[[]])([])

예제 출력 1

1

28

출처

• Olympiad > 한국정보올림피아드 > 한국정보올림피아드시․도지역본선 > 지역본선 2008 > 초등부 4번
• Olympiad > 한국정보올림피아드 > 한국정보올림피아드시․도지역본선 > 지역본선 2008 > 중등부 2번
  • 데이터를 추가한 사람: 906bc, djm03178, eatgugbab, leedongbin, sang7, sankim90
  • 잘못된 데이터를 찾은 사람: djm03178

알고리즘 분류

• 구현
• 자료 구조
• 스택
• 재귀

소스코드

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
40
41
42
43
44
45
46
47
48
49
50
51

import sys

input = sys.stdin.readline

input_string = list(input().rstrip())

stack = []


def solution(string):
    for bracket in string:

        if bracket == ')':
            tmp = 0
            while stack:
                top = stack.pop()
                if top == '(':
                    if tmp == 0:
                        stack.append(2)
                    else:
                        stack.append(tmp * 2)
                    break
                elif top == '[':
                    return 0
                else:
                    tmp += int(top)

        elif bracket == ']':
            tmp = 0
            while stack:
                top = stack.pop()
                if top == '[':
                    if tmp == 0:
                        stack.append(3)
                    else:
                        stack.append(tmp * 3)
                    break
                elif top == '(':
                    return 0
                else:
                    tmp += int(top)
        else:
            stack.append(bracket)
    return stack


if solution(input_string):
    print(0 if '(' in stack or '[' in stack else sum(stack))
else:
    print(0)

출처: [백준] 2167번 2차원 배열의 합

문제

2차원 배열이 주어졌을 때 (i, j) 위치부터 (x, y) 위치까지에 저장되어 있는 수들의 합을 구하는 프로그램을 작성하시오. 배열의 (i, j) 위치는 i행 j열을 나타낸다.

입력

첫째 줄에 배열의 크기 N, M(1 ≤ N, M ≤ 300)이 주어진다. 다음 N개의 줄에는 M개의 정수로 배열이 주어진다. 배열에 포함되어 있는 수는 절댓값이 10,000보다 작거나 같은 정수이다. 그 다음 줄에는 합을 구할 부분의 개수 K(1 ≤ K ≤ 10,000)가 주어진다. 다음 K개의 줄에는 네 개의 정수로 i, j, x, y가 주어진다(i ≤ x, j ≤ y).

출력

K개의 줄에 순서대로 배열의 합을 출력한다. 배열의 합은 231-1보다 작거나 같다.

예제 입력 1

1
2
3
4
5
6
7

2 3
1 2 4
8 16 32
3
1 1 2 3
1 2 1 2
1 3 2 3

예제 출력 1

1
2
3

63
2
36

출처

• 빠진 조건을 찾은 사람: iriszero
• 잘못된 데이터를 찾은 사람: tncks0121

알고리즘 분류

• 구현
• 누적 합

소스코드

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

import sys

input = sys.stdin.readline

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

dp = [[0] * (M + 1) for _ in range(N + 1)]
for i in range(1, N + 1):
    for j in range(1, M + 1):
        dp[i][j] = matrix[i - 1][j - 1] + dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1]

for _ in range(K):
    i, j, x, y = map(int, input().split())
    print(dp[x][y] - dp[x][j - 1] - dp[i - 1][y] + dp[i - 1][j - 1])

소스코드 (시간초과)

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

import sys

input = sys.stdin.readline

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

for _ in range(K):
    i, j, x, y = map(int, input().split())
    arr_sum = 0
    for a in range(i, x + 1):
        for b in range(j, y + 1):
            arr_sum += matrix[a - 1][b - 1]
    print(arr_sum)

출처: [백준] 3046번 R2

문제

두 숫자 R1과 R2가 있을 때, 두 수의 평균 S는 (R1+R2)/2와 같다. 상근이는 정인이 생일 선물로 두 숫자 R1과 R2를 주려고 한다. 생일 파티에서 상근이는 정인이에게 이 두 숫자를 말해주고, 정인이는 이 숫자를 받아 적는다. 그리고 나서 기쁜 마음으로 1년동안 이 숫자를 외우면서 산다.

상근이는 R1과 R2를 엄청난 고민 끝에 정했다. 작년에는 R1과 R2를 까먹어서 아무 숫자나 정해서 주었기 때문에, 올해는 까먹지 않기 위해서 평균 S도 같이 기억하려고 한다.

오늘은 정인이 생일이다. 5분 후에 상근이는 생일 선물로 두 숫자 R1과 R2를 말해주어야 하지만, 안타깝게도 R2를 까먹고 말았다. 하지만 R1과 S는 기억하고 있다!

상근이를 도와 R2가 몇 인지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 두 정수 R1과 S가 주어진다. 두 수는 -1000보다 크거나 같고, 1000보다 작거나 같다.

출력

첫째 줄에 R2를 출력한다.

예제 입력 1

1

11 15

예제 출력 1

1

19

예제 입력 2

1

4 3

예제 출력 2

1

2

출처

• Contest > Croatian Open Competition in Informatics > COCI 2006/2007 > Contest #2 1번
  • 문제를 번역한 사람: baekjoon

알고리즘 분류

• 수학
• 구현
• 사칙연산

소스코드

1
2
3
4

R1, S = map(int, input().split())

print(S * 2 - R1)

출처: [백준] 10797번 10부제

문제

서울시는 6월 1일부터 교통 혼잡을 막기 위해서 자동차 10부제를 시행한다. 자동차 10부제는 자동차 번호의 일의 자리 숫자와 날짜의 일의 자리 숫자가 일치하면 해당 자동차의 운행을 금지하는 것이다. 예를 들어, 자동차 번호의 일의 자리 숫자가 7이면 7일, 17일, 27일에 운행하지 못한다. 또한, 자동차 번호의 일의 자리 숫자가 0이면 10일, 20일, 30일에 운행하지 못한다.

여러분들은 일일 경찰관이 되어 10부제를 위반하는 자동차의 대수를 세는 봉사활동을 하려고 한다. 날짜의 일의 자리 숫자가 주어지고 5대의 자동차 번호의 일의 자리 숫자가 주어졌을 때 위반하는 자동차의 대수를 출력하면 된다.

입력

첫 줄에는 날짜의 일의 자리 숫자가 주어지고 두 번째 줄에는 5대의 자동차 번호의 일의 자리 숫자가 주어진다. 날짜와 자동차의 일의 자리 숫자는 모두 0에서 9까지의 정수 중 하나이다.

출력

주어진 날짜와 자동차의 일의 자리 숫자를 보고 10부제를 위반하는 차량의 대수를 출력한다.

예제 입력 1

1
2

1
1 2 3 4 5

예제 출력 1

1

1

예제 입력 2

1
2
3

1
1
1

예제 출력 2

1

2

예제 입력 3

1
2

5
1 3 0 7 4

예제 출력 3

1

0

출처

• Olympiad > 한국정보올림피아드 > 한국정보올림피아드시․도지역본선 > 지역본선 2015 > 초등부 1번
  • 데이터를 만든 사람: baekjoon
  • 잘못된 데이터를 찾은 사람: jh05013

알고리즘 분류

• 구현

소스코드

1
2
3
4
5
6
7
8
9
10
11

N = int(input())
car_list = list(map(int, input().split()))

count = 0

for car in car_list:
    if N == car:
        count += 1

print(count)

출처: [백준] 2902번 KMP는 왜 KMP일까?

문제

KMP 알고리즘이 KMP인 이유는 이를 만든 사람의 성이 Knuth, Morris, Prett이기 때문이다. 이렇게 알고리즘에는 발견한 사람의 성을 따서 이름을 붙이는 경우가 많다.

또 다른 예로, 유명한 비대칭 암호화 알고리즘 RSA는 이를 만든 사람의 이름이 Rivest, Shamir, Adleman이다.

사람들은 이렇게 사람 성이 들어간 알고리즘을 두 가지 형태로 부른다.

• 첫 번째는 성을 모두 쓰고, 이를 하이픈(-)으로 이어 붙인 것이다. 예를 들면, Knuth-Morris-Pratt이다. 이것을 긴 형태라고 부른다.
• 두 번째로 짧은 형태는 만든 사람의 성의 첫 글자만 따서 부르는 것이다. 예를 들면, KMP이다.

동혁이는 매일매일 자신이 한 일을 모두 메모장에 적어놓는다. 잠을 자기 전에, 오늘 하루 무엇을 했는지 되새겨 보는 것으로 하루를 마감한다.

하루는 이 메모를 보던 중, 지금까지 긴 형태와 짧은 형태를 섞어서 적어 놓은 것을 발견했다.

이렇게 긴 형태로 하루 일을 기록하다가는 메모장 가격이 부담되어 파산될 것이 뻔하기 때문에, 앞으로는 짧은 형태로 기록하려고 한다.

긴 형태의 알고리즘 이름이 주어졌을 때, 이를 짧은 형태로 바꾸어 출력하는 프로그램을 작성하시오.

입력

입력은 한 줄로 이루어져 있고, 최대 100글자의 영어 알파벳 대문자, 소문자, 그리고 하이픈 (‘-‘, 아스키코드 45)로만 이루어져 있다. 첫 번째 글자는 항상 대문자이다. 그리고, 하이픈 뒤에는 반드시 대문자이다. 그 외의 모든 문자는 모두 소문자이다.

출력

첫 줄에 짧은 형태 이름을 출력한다.

예제 입력 1

1

Knuth-Morris-Pratt

예제 출력 1

1

KMP

예제 입력 2

1

Mirko-Slavko

예제 출력 2

1

MS

예제 입력 3

1

Pasko-Patak

예제 출력 3

1

PP

출처

• Contest > Croatian Open Competition in Informatics > COCI 2009/2010 > Contest #4 1번
  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: eric00513
  • 빠진 조건을 찾은 사람: hoy9090

알고리즘 분류

• 구현
• 문자열

소스코드1

1
2
3
4
5
6
7

input_string = list(input().split('-'))
output_string = ''

for x in input_string:
    output_string += x[0]

print(output_string)

소스코드2

1
2
3
4
5
6
7
8
9

input_string = list(input().rstrip())
output_string = ''

for x in input_string:
    if 'A' <= x <= 'Z':
        output_string += x

print(output_string)

출처: [백준] 1032번 명령 프롬프트

문제

시작 -> 실행 -> cmd를 쳐보자. 검정 화면이 눈에 보인다. 여기서 dir이라고 치면 그 디렉토리에 있는 서브디렉토리와 파일이 모두 나온다. 이때 원하는 파일을 찾으려면 다음과 같이 하면 된다.

dir *.exe라고 치면 확장자가 exe인 파일이 다 나온다. “dir 패턴”과 같이 치면 그 패턴에 맞는 파일만 검색 결과로 나온다. 예를 들어, dir a?b.exe라고 검색하면 파일명의 첫 번째 글자가 a이고, 세 번째 글자가 b이고, 확장자가 exe인 것이 모두 나온다. 이때 두 번째 문자는 아무거나 나와도 된다. 예를 들어, acb.exe, aab.exe, apb.exe가 나온다.

이 문제는 검색 결과가 먼저 주어졌을 때, 패턴으로 뭘 쳐야 그 결과가 나오는지를 출력하는 문제이다. 패턴에는 알파벳과 “.” 그리고 “?”만 넣을 수 있다. 가능하면 ?을 적게 써야 한다. 그 디렉토리에는 검색 결과에 나온 파일만 있다고 가정하고, 파일 이름의 길이는 모두 같다.

입력

첫째 줄에 파일 이름의 개수 N이 주어진다. 둘째 줄부터 N개의 줄에는 파일 이름이 주어진다. N은 50보다 작거나 같은 자연수이고 파일 이름의 길이는 모두 같고 길이는 최대 50이다. 파일이름은 알파벳과 “.” 그리고 “?”로만 이루어져 있다.

출력

첫째 줄에 패턴을 출력하면 된다.

예제 입력 1

1
2
3
4

3
config.sys
config.inf
configures

예제 출력 1

1

config????

출처

• 문제를 번역한 사람: baekjoon

알고리즘 분류

• 구현
• 문자열

소스코드

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

import sys

input = sys.stdin.readline

N = int(input())
file_list = [list(input().rstrip()) for _ in range(N)]

input_word = file_list[-1]

for i in range(N - 1):
    for j in range(len(input_word)):
        if input_word[j] == file_list[i][j]:
            continue
        else:
            input_word[j] = '?'

print(''.join(input_word))