[백준] 2331번 반복수열
2021-06-20
Algorithm / Python

[백준] 2331번 반복수열

출처: [백준] 2331번 반복수열

시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 9795 4407 3250 44.176%

문제

다음과 같이 정의된 수열이 있다.

  • D[1] = A
  • D[n] = D[n-1]의 각 자리의 숫자를 P번 곱한 수들의 합

예를 들어 A=57, P=2일 때, 수열 D는 {57, 74(=5^2+7^2=25+49), 65, 61, 37, 58, 89, 145, 42, 20, 4, 16, 37, …}이 된다. 그 뒤에는 앞서 나온 수들(57부터가 아니라 58부터)이 반복된다.

이와 같은 수열을 계속 구하다 보면 언젠가 이와 같은 반복수열이 된다. 이때, 반복되는 부분을 제외했을 때, 수열에 남게 되는 수들의 개수를 구하는 프로그램을 작성하시오. 위의 예에서는 {57, 74, 65, 61}의 네 개의 수가 남게 된다.

입력

첫째 줄에 A(1 ≤ A ≤ 9999), P(1 ≤ P ≤ 5)가 주어진다.

출력

첫째 줄에 반복되는 부분을 제외했을 때, 수열에 남게 되는 수들의 개수를 출력한다.

예제 입력 1

1
57 2

예제 출력 1

1
4

출처

-

알고리즘 분류

소스코드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
import sys

input = sys.stdin.readline

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

stack = [A]
temp = 0
while 1:
    value = str(stack[-1])
    temp = 0
    for i in range(len(value)):
        temp += int(value[i]) ** P

    if temp in stack:
        value = str(stack[-1])
        temp = 0
        for i in range(len(value)):
            temp += int(value[i]) ** P
        break
    else:
        stack.append(temp)

print(stack.index(temp))

소스코드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
import sys

input = sys.stdin.readline

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

stack = [A]
removed_stack = []

while stack:
    value = str(stack[-1])
    temp = 0
    for i in range(len(value)):
        temp += int(value[i]) ** P

    if temp not in stack:
        stack.append(temp)
    else:
        stack.append(temp)
        if temp in removed_stack:
            break
        else:
            removed_stack.append(temp)

print(len(set(stack) - set(removed_stack)))

[백준] 1051번 숫자 정사각형
2021-06-20
Algorithm / Python

[백준] 1051번 숫자 정사각형

출처: [백준] 1051번 숫자 정사각형

시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 10235 3747 3173 37.528%

문제

N*M크기의 직사각형이 있다. 각 칸은 한 자리 숫자가 적혀 있다. 이 직사각형에서 꼭짓점에 쓰여 있는 수가 모두 같은 가장 큰 정사각형을 찾는 프로그램을 작성하시오. 이때, 정사각형은 행 또는 열에 평행해야 한다.

입력

첫째 줄에 N과 M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 수가 주어진다.

출력

첫째 줄에 정답 정사각형의 크기를 출력한다.

예제 입력 1

1
2
3
4
3 5
42101
22100
22101

예제 출력 1

1
9

출처

  • 빠진 조건을 찾은 사람: adh0463
  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: jh05013

알고리즘 분류

소스코드

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

input = sys.stdin.readline

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

max_edge = min(N, M)
result = 0
for i in range(N):
    for j in range(M):
        for k in range(max_edge):
            if i + k < N and j + k < M:
                if rectangle[i][j] == rectangle[i][j + k] == rectangle[i + k][j] == rectangle[i + k][j + k]:
                    result = max(result, (k + 1) ** 2)
print(result)

[백준] 3085번 사탕게임
2021-06-19
Algorithm / Python

[백준] 3085번 사탕게임

출처: [백준] 3085번 사탕게임

시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 17749 5491 3869 30.534%

문제

상근이는 어렸을 적에 “봄보니 (Bomboni)” 게임을 즐겨했다.

가장 처음에 N×N크기에 사탕을 채워 놓는다. 사탕의 색은 모두 같지 않을 수도 있다. 상근이는 사탕의 색이 다른 인접한 두 칸을 고른다. 그 다음 고른 칸에 들어있는 사탕을 서로 교환한다. 이제, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고른 다음 그 사탕을 모두 먹는다.

사탕이 채워진 상태가 주어졌을 때, 상근이가 먹을 수 있는 사탕의 최대 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 보드의 크기 N이 주어진다. (3 ≤ N ≤ 50)

다음 N개 줄에는 보드에 채워져 있는 사탕의 색상이 주어진다. 빨간색은 C, 파란색은 P, 초록색은 Z, 노란색은 Y로 주어진다.

사탕의 색이 다른 인접한 두 칸이 존재하는 입력만 주어진다.

출력

첫째 줄에 상근이가 먹을 수 있는 사탕의 최대 개수를 출력한다.

예제 입력 1

1
2
3
4
3
CCP
CCP
PPC

예제 출력 1

1
3

예제 입력 2

1
2
3
4
5
4
PPPP
CYZY
CCPY
PPCC

예제 출력 2

1
4

예제 입력 3

1
2
3
4
5
6
5
YCPZY
CYZZP
CCPPP
YCYZC
CPPZZ

예제 출력 3

1
4

힌트

예제 3의 경우 4번 행의 Y와 C를 바꾸면 사탕 네 개를 먹을 수 있다.

출처

알고리즘 분류

소스코드

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
52
import sys

input = sys.stdin.readline


def check(arr):
    n = len(board)
    answer = 1
    for i in range(n):
        cnt = 1
        for j in range(1, n):  # 열 순회하면서 연속 숫자 세기
            if arr[i][j] == arr[i][j - 1]:  # 이전것과 같으면 cnt+1
                cnt += 1
            else:  # 이전 것과 다르면  cnt=1 초기화
                cnt = 1
            if cnt > answer:
                answer = cnt

        cnt = 1
        for j in range(1, n):  # 행 순회하면서 연속 숫자 세기
            if arr[j][i] == arr[j - 1][i]:  # 이전것과 같으면 cnt+1
                cnt += 1
            else:  # 이전 것과 다르면  cnt=1 초기화
                cnt = 1
            if cnt > answer:
                answer = cnt

    return answer


N = int(input())
board = [list(input().rstrip()) for _ in range(N)]
result = 0

for i in range(N):
    for j in range(N):
        if j + 1 < N:  # 열 체크
            board[i][j], board[i][j + 1] = board[i][j + 1], board[i][j]  # 인접 교환
            temp = check(board)
            if temp > result:
                result = temp
            board[i][j], board[i][j + 1] = board[i][j + 1], board[i][j]  # 원복

        if i + 1 < N:  # 행 체크
            board[i][j], board[i + 1][j] = board[i + 1][j], board[i][j]  # 인접 교환
            temp = check(board)
            if temp > result:
                result = temp
            board[i][j], board[i + 1][j] = board[i + 1][j], board[i][j]  # 원복

print(result)

[백준] 2693번 N번째 큰 수
2021-06-19
Algorithm / Python

[백준] 2693번 N번째 큰 수

출처: [백준] 2693번 N번째 큰 수

시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 32 MB 3791 3044 2767 81.502%

문제

배열 A가 주어졌을 때, N번째 큰 값을 출력하는 프로그램을 작성하시오.

배열 A의 크기는 항상 10이고, 자연수만 가지고 있다. N은 항상 3이다.

입력

첫째 줄에 테스트 케이스의 개수 T(1 <= T <= 1,000)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 배열 A의 원소 10개가 공백으로 구분되어 주어진다. 이 원소는 1보다 크거나 같고, 1,000보다 작거나 같은 자연수이다.

출력

각 테스트 케이스에 대해 한 줄에 하나씩 배열 A에서 3번째 큰 값을 출력한다.

예제 입력 1

1
2
3
4
5
4
1 2 3 4 5 6 7 8 9 1000
338 304 619 95 343 496 489 116 98 127
931 240 986 894 826 640 965 833 136 138
940 955 364 188 133 254 501 122 768 408

예제 출력 1

1
2
3
4
8
489
931
768

출처

알고리즘 분류

소스코드

1
2
3
4
5
6
7
8
9
10
11
import sys

input = sys.stdin.readline

T = int(input())

for _ in range(T):
    arr = list(map(int, input().split()))
    arr.sort(reverse=True)
    print(arr[2])

[백준] 10973번 이전 순열
2021-06-18
Algorithm / Python

[백준] 10973번 이전 순열

출처: [백준] 10973번 이전 순열

시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 7635 4771 3960 64.780%

문제

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

1
2
5
5 4 3 2 1

예제 출력 2

1
5 4 3 1 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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
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)



------------메모리초과
import sys
from itertools import permutations

input = sys.stdin.readline

N = int(input())
compare_list = list(map(int, input().split()))
num_list = [i for i in range(1, N + 1)]

perm_list = list(permutations(num_list))
for i in range(len(perm_list)):
    if list(perm_list[i]) == compare_list:
        if i==0:
            print(-1)
        else:
            for num in perm_list[i-1]:
                print(num, end=" ")

[백준] 10972번 다음 순열
2021-06-18
Algorithm / Python

[백준] 10972번 다음 순열

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

시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 17068 7204 5176 43.001%

문제

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

출처

알고리즘 분류

소스코드

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번 쉽게 푸는 문제
2021-06-17
Algorithm / Python

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

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

시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 10628 5891 5197 57.559%

문제

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

이 문제는 다음과 같다. 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

출처

알고리즘 분류

소스코드

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
2021-06-17
Algorithm / Python

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

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

시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
0.15 초 128 MB 12262 5639 4743 51.209%

문제

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

출처

알고리즘 분류

소스코드

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번 집합
2021-06-16
Algorithm / Python

[백준] 11723번 집합

출처: [백준] 11723번 집합

시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1.5 초 4 MB (하단 참고) 32627 10094 7070 30.218%

문제

비어있는 공집합 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

출처

알고리즘 분류

소스코드

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번 괄호의 값
2021-06-16
Algorithm / Python

[백준] 2504번 괄호의 값

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

시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 29463 7308 5555 27.818%

문제

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

출처

알고리즘 분류

소스코드

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)

팔로우

카테고리

최근 글

태그

알고리즘190
Python182
백준172
IT뉴스92
IT Issues92
구현65
자료구조55
네이버39
카카오30
스택26
JS24
Javascript24
자바스크립트24
큐22
문자열20
수학16
Programming16
애플15
그래프 탐색15
해시15
핀테크14
너비 우선 탐색14
BFS14
프로그래머스14
Spring Boot14
Java14
그래프13
DFS13
구글12
그리디12
×