[백준] 1543번 문서 검색

[백준] 1543번 문서 검색

출처: [백준] 1543번 문서 검색


시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 10226 3896 3092 37.671%

문제

세준이는 영어로만 이루어진 어떤 문서를 검색하는 함수를 만들려고 한다. 이 함수는 어떤 단어가 총 몇 번 등장하는지 세려고 한다. 그러나, 세준이의 함수는 중복되어 세는 것은 빼고 세야 한다. 예를 들어, 문서가 abababa이고, 그리고 찾으려는 단어가 ababa라면, 세준이의 이 함수는 이 단어를 0번부터 찾을 수 있고, 2번부터도 찾을 수 있다. 그러나 동시에 셀 수는 없다.

세준이는 문서와 검색하려는 단어가 주어졌을 때, 그 단어가 최대 몇 번 중복되지 않게 등장하는지 구하는 프로그램을 작성하시오.


입력

첫 번째 줄에 알파벳 대소문자, 공백으로 구성된 문자열이 주어진다. 문자열의 길이는 최대 1,000자이다. 문자열첫째 줄에 문서가 주어진다. 문서의 길이는 최대 2500이다. 둘째 줄에 검색하고 싶은 단어가 주어진다. 이 길이는 최대 50이다. 문서와 단어는 알파벳 소문자와 공백으로 이루어져 있다.


출력

첫째 줄에 중복되지 않게 최대 몇 번 등장하는지 출력한다.


예제 입력 1

1
2
ababababa
aba

예제 출력 1

1
2

예제 입력 2

1
2
a a a a a
a a

예제 출력 2

1
2

출처


알고리즘 분류


소스코드1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import sys
from collections import Counter

input = sys.stdin.readline

doc = input().rstrip()
word = input().rstrip()
doc = doc.replace(word, "?")

temp = dict(Counter(list(doc)))
if '?' in temp:
print(temp['?'])
else:
print(0)

소스코드2

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

input = sys.stdin.readline

doc = input().rstrip()
word = input().rstrip()

count = 0
idx = 0

while idx <= len(doc) - len(word):
if doc[idx:idx + len(word)] == word:
count += 1
idx += len(word)
else:
idx += 1
print(count)

[백준] 2503번 숫자 야구

[백준] 2503번 숫자 야구

출처: [백준] 2503번 숫자 야구


시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 9137 4152 3430 45.923%

문제

정보문화진흥원 정보 영재 동아리에서 동아리 활동을 하던 영수와 민혁이는 쉬는 시간을 틈타 숫자야구 게임을 하기로 했다.

  • 영수는 1에서 9까지의 서로 다른 숫자 세 개로 구성된 세 자리 수를 마음속으로 생각한다. (예: 324)
  • 민혁이는 1에서 9까지의 서로 다른 숫자 세 개로 구성된 세 자리 수를 영수에게 묻는다. (예: 123)
  • 민혁이가 말한 세 자리 수에 있는 숫자들 중 하나가 영수의 세 자리 수의 동일한 자리에 위치하면 스트라이크 한 번으로 센다. 숫자가 영수의 세 자리 수에 있긴 하나 다른 자리에 위치하면 볼 한 번으로 센다.

예) 영수가 324를 갖고 있으면

  • 429는 1 스트라이크 1 볼이다.
  • 241은 0 스트라이크 2 볼이다.
  • 924는 2 스트라이크 0 볼이다.
  • 영수는 민혁이가 말한 수가 몇 스트라이크 몇 볼인지를 답해준다.
  • 민혁이가 영수의 세 자리 수를 정확하게 맞추어 3 스트라이크가 되면 게임이 끝난다. 아니라면 민혁이는 새로운 수를 생각해 다시 영수에게 묻는다.

현재 민혁이와 영수는 게임을 하고 있는 도중에 있다. 민혁이가 영수에게 어떤 수들을 물어보았는지, 그리고 각각의 물음에 영수가 어떤 대답을 했는지가 입력으로 주어진다. 이 입력을 바탕으로 여러분은 영수가 생각하고 있을 가능성이 있는 수가 총 몇 개인지를 알아맞혀야 한다.

아래와 같은 경우를 생각해보자.

  • 민혁: 123
  • 영수: 1 스트라이크 1 볼.
  • 민혁: 356
  • 영수: 1 스트라이크 0 볼.
  • 민혁: 327
  • 영수: 2 스트라이크 0 볼.
  • 민혁: 489
  • 영수: 0 스트라이크 1 볼.

이때 가능한 답은 324와 328, 이렇게 두 가지이다.

영수는 동아리의 규율을 잘 따르는 착한 아이라 민혁이의 물음에 곧이곧대로 정직하게 답한다. 그러므로 영수의 답들에는 모순이 없다.

민혁이의 물음들과 각각의 물음에 대한 영수의 답이 입력으로 주어질 때 영수가 생각하고 있을 가능성이 있는 답의 총 개수를 출력하는 프로그램을 작성하시오.


입력

첫째 줄에는 민혁이가 영수에게 몇 번이나 질문을 했는지를 나타내는 1 이상 100 이하의 자연수 N이 주어진다. 이어지는 N개의 줄에는 각 줄마다 민혁이가 질문한 세 자리 수와 영수가 답한 스트라이크 개수를 나타내는 정수와 볼의 개수를 나타내는 정수, 이렇게 총 세 개의 정수가 빈칸을 사이에 두고 주어진다.


출력

첫 줄에 영수가 생각하고 있을 가능성이 있는 답의 총 개수를 출력한다.


예제 입력 1

1
2
3
4
5
4
123 1 1
356 1 0
327 2 0
489 0 1

예제 출력 1

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
import sys
from itertools import permutations

input = sys.stdin.readline

num = [1, 2, 3, 4, 5, 6, 7, 8, 9]
cases = list(permutations(num, 3))

N = int(input())
for _ in range(N):
ques, s_c, b_c = map(int, input().split())
ques = list(str(ques))

temp_cases = []
for i in range(len(cases)):
strike, ball = 0, 0
for j in range(3):
if cases[i][j] == int(ques[j]):
strike += 1
elif int(ques[j]) in cases[i]:
ball += 1
if s_c == strike and b_c == ball:
temp_cases.append(cases[i])

# 한 줄 끝나고, 맞은 케이스만 사용할 수 있도록
cases = temp_cases

print(len(cases))

[백준] 2304번 창고 다각형

[백준] 2304번 창고 다각형

출처: [백준] 2304번 창고 다각형


시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 4418 1870 1510 44.360%

문제

N 개의 막대 기둥이 일렬로 세워져 있다. 기둥들의 폭은 모두 1 m이며 높이는 다를 수 있다. 이 기둥들을 이용하여 양철로 된 창고를 제작하려고 한다. 창고에는 모든 기둥이 들어간다. 이 창고의 지붕을 다음과 같이 만든다.

  1. 지붕은 수평 부분과 수직 부분으로 구성되며, 모두 연결되어야 한다.
  2. 지붕의 수평 부분은 반드시 어떤 기둥의 윗면과 닿아야 한다.
  3. 지붕의 수직 부분은 반드시 어떤 기둥의 옆면과 닿아야 한다.
  4. 지붕의 가장자리는 땅에 닿아야 한다.
  5. 비가 올 때 물이 고이지 않도록 지붕의 어떤 부분도 오목하게 들어간 부분이 없어야 한다.

그림 1은 창고를 옆에서 본 모습을 그린 것이다. 이 그림에서 굵은 선으로 표시된 부분이 지붕에 해당되고, 지붕과 땅으로 둘러싸인 다각형이 창고를 옆에서 본 모습이다. 이 다각형을 창고 다각형이라고 하자.

img

그림1 . 기둥과 지붕(굵은 선)의 예

창고 주인은 창고 다각형의 면적이 가장 작은 창고를 만들기를 원한다. 그림 1에서 창고 다각형의 면적은 98 ㎡이고, 이 경우가 가장 작은 창고 다각형이다.

기둥들의 위치와 높이가 주어질 때, 가장 작은 창고 다각형의 면적을 구하는 프로그램을 작성하시오.


입력

첫 줄에는 기둥의 개수를 나타내는 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 그 다음 N 개의 줄에는 각 줄에 각 기둥의 왼쪽 면의 위치를 나타내는 정수 L과 높이를 나타내는 정수 H가 한 개의 빈 칸을 사이에 두고 주어진다. L과 H는 둘 다 1 이상 1,000 이하이다.


출력

첫 줄에 창고 다각형의 면적을 나타내는 정수를 출력한다.


예제 입력 1

1
2
3
4
5
6
7
8
7
2 4
11 4
15 8
4 6
5 3
8 10
13 6

예제 출력 1

1
98

출처


알고리즘 분류


소스코드

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

input = sys.stdin.readline

N = int(input())
pillars = []
for _ in range(N):
idx, height = map(int, input().split())
pillars.append((idx, height))

pillars.sort(key=lambda x: x[0]) # 정렬

max_pillar = max(pillars, key=lambda x: x[1]) # 가장 높은 기둥찾기

# 땅에 기둥세우기
area = [0] * (pillars[-1][0] + 1)
for idx, height in pillars:
area[idx] = height
max_index = area.index(max_pillar[1]) # 높은 기둥의 인덱스찾기

temp = 0
total = 0
# 왼쪽부터 가장 높은 기둥까지
for i in range(max_index + 1):
if area[i] > temp:
temp = area[i]
total += temp

temp = 0
# 오른쪽부터 가장높은 기둥까지
for i in range(pillars[-1][0], max_index, -1):
if area[i] > temp:
temp = area[i]
total += temp

print(total)

[백준] 2002번 추월

[백준] 2002번 추월

출처: [백준] 2002번 추월


시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 2040 894 757 44.766%

문제

대한민국을 비롯한 대부분의 나라에서는 터널 내에서의 차선 변경을 법률로 금하고 있다. 조금만 관찰력이 있는 학생이라면 터널 내부에서는 차선이 파선이 아닌 실선으로 되어 있다는 것을 알고 있을 것이다. 이는 차선을 변경할 수 없음을 말하는 것이고, 따라서 터널 내부에서의 추월은 불가능하다.

소문난 명콤비 경찰 대근이와 영식이가 추월하는 차량을 잡기 위해 한 터널에 투입되었다. 대근이는 터널의 입구에, 영식이는 터널의 출구에 각각 잠복하고, 대근이는 차가 터널에 들어가는 순서대로, 영식이는 차가 터널에서 나오는 순서대로 각각 차량 번호를 적어 두었다.

N개의 차량이 지나간 후, 대근이와 영식이는 자신들이 적어 둔 차량 번호의 목록을 보고, 터널 내부에서 반드시 추월을 했을 것으로 여겨지는 차들이 몇 대 있다는 것을 알게 되었다. 대근이와 영식이를 도와 이를 구하는 프로그램을 작성해 보자.


입력

입력은 총 2N+1개의 줄로 이루어져 있다. 첫 줄에는 차의 대수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 대근이가 적은 차량 번호 목록이 주어지고, N+2째 줄부터 N개의 줄에는 영식이가 적은 차량 번호 목록이 주어진다. 각 차량 번호는 6글자 이상 8글자 이하의 문자열로, 영어 대문자(‘A’-‘Z’)와 숫자(‘0’-‘9’)로만 이루어져 있다.

같은 차량 번호가 두 번 이상 주어지는 경우는 없다.


출력

첫째 줄에 터널 내부에서 반드시 추월을 했을 것으로 여겨지는 차가 몇 대인지 출력한다.


예제 입력 1

1
2
3
4
5
6
7
8
9
4
ZG431SN
ZG5080K
ST123D
ZG206A
ZG206A
ZG431SN
ZG5080K
ST123D

예제 출력 1

1
1

예제 입력 2

1
2
3
4
5
6
7
8
9
10
11
5
ZG508OK
PU305A
RI604B
ZG206A
ZG232ZF
PU305A
ZG232ZF
ZG206A
ZG508OK
RI604B

예제 출력 2

1
3

예제 입력 3

1
2
3
4
5
6
7
8
9
10
11
5
ZG206A
PU234Q
OS945CK
ZG431SN
ZG5962J
ZG5962J
OS945CK
ZG206A
PU234Q
ZG431SN

예제 출력 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
import sys

input = sys.stdin.readline

N = int(input())

count = 0
input_car = {}
output_car = []

for i in range(N):
input_car[input().rstrip()] = i

for i in range(N):
output_car.append(input().rstrip())

for i in range(N - 1):
for j in range(i + 1, N):
if input_car[output_car[i]] > input_car[output_car[j]]:
count += 1
break

print(count)

[백준] 5568번 카드 놓기

[백준] 5568번 카드 놓기

출처: [백준] 5568번 카드 놓기


시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 2813 1519 1197 53.082%

문제

상근이는 카드 n(4 ≤ n ≤ 10)장을 바닥에 나란히 놓고 놀고있다. 각 카드에는 1이상 99이하의 정수가 적혀져 있다. 상근이는 이 카드 중에서 k(2 ≤ k ≤ 4)장을 선택하고, 가로로 나란히 정수를 만들기로 했다. 상근이가 만들 수 있는 정수는 모두 몇 가지일까?

예를 들어, 카드가 5장 있고, 카드에 쓰여 있는 수가 1, 2, 3, 13, 21라고 하자. 여기서 3장을 선택해서 정수를 만들려고 한다. 2, 1, 13을 순서대로 나열하면 정수 2113을 만들 수 있다. 또, 21, 1, 3을 순서대로 나열하면 2113을 만들 수 있다. 이렇게 한 정수를 만드는 조합이 여러 가지 일 수 있다.

n장의 카드에 적힌 숫자가 주어졌을 때, 그 중에서 k개를 선택해서 만들 수 있는 정수의 개수를 구하는 프로그램을 작성하시오.


입력

첫째 줄에 n이, 둘째 줄에 k가 주어진다. 셋째 줄부터 n개 줄에는 카드에 적혀있는 수가 주어진다.


출력

첫째 줄에 상근이가 만들 수 있는 정수의 개수를 출력한다.


예제 입력 1

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

예제 출력 1

1
7

예제 입력 2

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

예제 출력 2

1
68

힌트

예제 1의 경우 상근이는 11, 12, 21, 112, 121, 122, 212를 만들 수 있다.


출처

img


알고리즘 분류


소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import sys
from itertools import permutations

input = sys.stdin.readline

N = int(input())
K = int(input())

card_list = []
for _ in range(N):
card_list.append(input().rstrip())

result = []
for x in permutations(card_list, K):
result.append(''.join(x))

result = list(set(result))
print(len(result))

[백준] 2309번 일곱 난쟁이

[백준] 2309번 일곱 난쟁이

출처: [백준] 2309번 일곱 난쟁이


시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 58006 24046 17750 43.684%

문제

왕비를 피해 일곱 난쟁이들과 함께 평화롭게 생활하고 있던 백설공주에게 위기가 찾아왔다. 일과를 마치고 돌아온 난쟁이가 일곱 명이 아닌 아홉 명이었던 것이다.

아홉 명의 난쟁이는 모두 자신이 “백설 공주와 일곱 난쟁이”의 주인공이라고 주장했다. 뛰어난 수학적 직관력을 가지고 있던 백설공주는, 다행스럽게도 일곱 난쟁이의 키의 합이 100이 됨을 기억해 냈다.

아홉 난쟁이의 키가 주어졌을 때, 백설공주를 도와 일곱 난쟁이를 찾는 프로그램을 작성하시오.


입력

아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다.


출력

일곱 난쟁이의 키를 오름차순으로 출력한다. 일곱 난쟁이를 찾을 수 없는 경우는 없다.


예제 입력 1

1
2
3
4
5
6
7
8
9
20
7
23
19
10
15
25
8
13

예제 출력 1

1
2
3
4
5
6
7
7
8
10
13
19
20
23

출처


알고리즘 분류


소스코드1

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

input = sys.stdin.readline

dwarfs = [int(input()) for _ in range(9)]
dwarfs.sort()

nPr = combinations(dwarfs, 7)

temp = []
for case in list(nPr):
if sum(case) == 100:
temp = case
break
for x in temp:
print(x)

소스코드2

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

input = sys.stdin.readline

dwarfs = [int(input()) for _ in range(9)]
dwarfs.sort()

height_sum = sum(dwarfs)
delete_element1 = 0
delete_element2 = 0

for i in range(9):
for j in range(i + 1, 9):
if height_sum - (dwarfs[i] + dwarfs[j]) == 100:
delete_element1 = dwarfs[i]
delete_element2 = dwarfs[j]
break

for dwarf in dwarfs:
if dwarf == delete_element1 or dwarf == delete_element2:
continue
else:
print(dwarf)
[백준] 1436번 영화감독 숌

[백준] 1436번 영화감독 숌

출처: [백준] 1436번 영화감독 숌


시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 31210 13703 11247 44.456%

문제

666은 종말을 나타내는 숫자라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타워즈를 만들 때, 스타워즈 1, 스타워즈 2, 스타워즈 3, 스타워즈 4, 스타워즈 5, 스타워즈 6과 같이 이름을 지었고, 피터 잭슨은 반지의 제왕을 만들 때, 반지의 제왕 1, 반지의 제왕 2, 반지의 제왕 3과 같이 영화 제목을 지었다.

하지만 숌은 자신이 조지 루카스와 피터 잭슨을 뛰어넘는다는 것을 보여주기 위해서 영화 제목을 좀 다르게 만들기로 했다.

종말의 숫자란 어떤 수에 6이 적어도 3개이상 연속으로 들어가는 수를 말한다. 제일 작은 종말의 숫자는 666이고, 그 다음으로 큰 수는 1666, 2666, 3666, …. 과 같다.

따라서, 숌은 첫 번째 영화의 제목은 세상의 종말 666, 두 번째 영화의 제목은 세상의 종말 1666 이렇게 이름을 지을 것이다. 일반화해서 생각하면, N번째 영화의 제목은 세상의 종말 (N번째로 작은 종말의 숫자) 와 같다.

숌이 만든 N번째 영화의 제목에 들어간 숫자를 출력하는 프로그램을 작성하시오. 숌은 이 시리즈를 항상 차례대로 만들고, 다른 영화는 만들지 않는다.


입력

첫째 줄에 숫자 N이 주어진다. N은 10,000보다 작거나 같은 자연수이다.


출력

첫째 줄에 N번째 영화의 제목에 들어간 수를 출력한다.


예제 입력 1

1
2

예제 출력 1

1
1666

힌트


출처

  • 문제를 번역한 사람: baekjoon
  • 어색한 표현을 찾은 사람: mwy3055

알고리즘 분류


시간 제한


풀이

  • 666,1666,2666,3666,4666,5666,6660,6661…….

소스코드

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

input = sys.stdin.readline

N = int(input())

title = 666
cnt = 0
while True:
if '666' in str(title):
cnt += 1
if cnt == N:
print(title)
break
title += 1

[백준] 2447번 별 찍기-10

[백준] 2447번 별 찍기-10

출처: [백준] 2447번 별 찍기-10


시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 37375 17060 13949 46.314%

문제

재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, …)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다.

크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 하나씩 있는 패턴이다.

1
2
3
***
* *
***

N이 3보다 클 경우, 크기 N의 패턴은 공백으로 채워진 가운데의 (N/3)×(N/3) 정사각형을 크기 N/3의 패턴으로 둘러싼 형태이다. 예를 들어 크기 27의 패턴은 예제 출력 1과 같다.


입력

첫째 줄에 N이 주어진다. N은 3의 거듭제곱이다. 즉 어떤 정수 k에 대해 N=3k이며, 이때 1 ≤ k < 8이다.


출력

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


예제 입력 1

1
27

예제 출력 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
***************************
* ** ** ** ** ** ** ** ** *
***************************
*** ****** ****** ***
* * * ** * * ** * * *
*** ****** ****** ***
***************************
* ** ** ** ** ** ** ** ** *
***************************
********* *********
* ** ** * * ** ** *
********* *********
*** *** *** ***
* * * * * * * *
*** *** *** ***
********* *********
* ** ** * * ** ** *
********* *********
***************************
* ** ** ** ** ** ** ** ** *
***************************
*** ****** ****** ***
* * * ** * * ** * * *
*** ****** ****** ***
***************************
* ** ** ** ** ** ** ** ** *
***************************

힌트


출처

  • 문제를 만든 사람: baekjoon
  • 문제를 다시 작성한 사람: jh05013

알고리즘 분류


시간 제한


풀이

  • 1, 4, 7, 10, 13, 16, 19, 22, 25 …. 3으로 나눈 나머지가 1인 부분이 공백
  • 전체를 봤을때, 3줄씩 한 세트라고 하면, 3, 4, 5, 12, 13, 14, 21, 22, 23…. (n//3)%3==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
28
29
import sys

input = sys.stdin.readline

N = int(input())
arr = [['*'] * N for _ in range(N)] # output array 생성

temp = N
cnt = 0
while temp != 1: # 입력받은 n이 3의 몇승?
temp /= 3
cnt += 1


'''
1, 4, 7, 10, 13, 16, 19, 22, 25 .... 3으로 나눈 나머지가 1인 부분이 공백
전체를 봤을때, 3줄씩 한 세트라고 하면, 3, 4, 5, 12, 13, 14, 21, 22, 23.... (n//3)%3==1인 부분이 공백
'''
for i in range(cnt):
idx = []
for j in range(N):
if (j // 3 ** i) % 3 == 1:
idx.append(j)
for row in idx:
for col in idx:
arr[row][col] = ' '

print('\n'.join([''.join([str(i) for i in row]) for row in arr]))

[백준] 1018번 체스판 다시 칠하기

[백준] 1018번 체스판 다시 칠하기

출처: [백준] 1018번 체스판 다시 칠하기


시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 37375 17060 13949 46.314%

문제

지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 MN 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 88 크기의 체스판으로 만들려고 한다.

체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다.

보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 8x8 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했다. 당연히 8x8 크기는 아무데서나 골라도 된다. 지민이가 다시 칠해야 하는 정사각형의 최소 개수를 구하는 프로그램을 작성하시오.


입력

첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다.


출력

첫째 줄에 지민이가 다시 칠해야 하는 정사각형 개수의 최솟값을 출력한다.


예제 입력 1

1
2
3
4
5
6
7
8
9
8 8
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBBBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW

예제 출력 1

1
1

예제 입력 2

1
2
3
4
5
6
7
8
9
10
11
10 13
BBBBBBBBWBWBW
BBBBBBBBBWBWB
BBBBBBBBWBWBW
BBBBBBBBBWBWB
BBBBBBBBWBWBW
BBBBBBBBBWBWB
BBBBBBBBWBWBW
BBBBBBBBBWBWB
WWWWWWWWWWBWB
WWWWWWWWWWBWB

예제 출력 2

1
12

힌트


출처

  • 문제를 번역한 사람:
  • 데이터를 추가한 사람:
  • 문제를 다시 작성한 사람: jh05013

알고리즘 분류


시간 제한


풀이


소스코드

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

input = sys.stdin.readline

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


def check_BW(slice_board):
# print(slice_board)
black_cnt = 0 # black 시작 [bwbwbwbw],[wbwbwbwb]
for row in range(8):
for col in range(8):
if (row % 2 == 0 and col % 2 == 0) or (row % 2 == 1 and col % 2 == 1):
if slice_board[row][col] != "B":
black_cnt += 1
if (row % 2 == 0 and col % 2 == 1) or (row % 2 == 1 and col % 2 == 0):
if slice_board[row][col] != "W":
black_cnt += 1

white_cnt = 0 # white 시작 [wbwbwbwb],[bwbwbwbw]
for row in range(8):
for col in range(8):
if (row % 2 == 0 and col % 2 == 0) or (row % 2 == 1 and col % 2 == 1):
if slice_board[row][col] != "W":
white_cnt += 1
if (row % 2 == 0 and col % 2 == 1) or (row % 2 == 1 and col % 2 == 0):
if slice_board[row][col] != "B":
white_cnt += 1

return min(black_cnt, white_cnt)


check = []
for row in range(N - 7):
for col in range(M - 7):
cnt1, cnt2 = 0, 0
# 체스판 경우의 수 slicing
c = [board[row + i][col:col + 8] for i in range(8)]
# c = [c[(0 + col):(8 + col)] for c in board[(0 + row):(8 + row)]]
check.append(check_BW(c))
print(min(check))

[백준] 18868번 멀티버스Ⅰ

[백준] 18868번 멀티버스Ⅰ

출처: [백준] 18868번 멀티버스Ⅰ


시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 (추가 시간 없음) 512 MB 882 494 293 62.876%

문제

M개의 우주가 있고, 각 우주에는 1부터 N까지 번호가 매겨진 행성이 N개 있다. 행성의 크기를 알고 있을때, 균등한 우주의 쌍이 몇 개인지 구해보려고 한다. 구성이 같은데 순서만 다른 우주의 쌍은 한 번만 센다.

두 우주 A와 B가 있고, 우주 A에 있는 행성의 크기는 A1, A2, …, AN, 우주 B에 있는 행성의 크기는 B1, B2, …, BN라고 하자. 두 우주의 행성 크기가 모든 1 ≤ i, j ≤ N에 대해서 아래와 같은 조건을 만족한다면, 두 우주를 균등하다고 한다.

  • Ai < Aj → Bi < Bj
  • Ai = Aj → Bi = Bj
  • Ai > Aj → Bi > Bj

입력

첫째 줄에 우주의 개수 M과 각 우주에 있는 행성의 개수 N이 주어진다. 둘째 줄부터 M개의 줄에 공백으로 구분된 행성의 크기가 한 줄에 하나씩 1번 우주부터 차례대로 주어진다.


출력

첫째 줄에 균등한 우주의 쌍의 개수를 출력한다.


제한

  • 2 ≤ M ≤ 10
  • 3 ≤ N ≤ 100
  • 1 ≤ 행성의 크기 ≤ 10,000

예제 입력 1

1
2
3
2 3
1 3 2
12 50 31

예제 출력 1

1
1
  • (A, B) = (1, 2)
    • A1 = 1 < A2 = 3 이고, B1 = 12 < B2 = 50
    • A1 = 1 < A3 = 2 이고, B1 = 12 < B3 = 31
    • A2 = 3 > A3 = 2 이고, B2 = 50 > B3 = 31
  • 모든 1 ≤ i, j ≤ N에 대해서 만족한다.

예제 입력 2

1
2
3
2 3
1 3 2
12 50 10

예제 출력 2

1
0
  • (A, B) = (1, 2)
    • A1 = 1 < A3 = 2 인데, B1 = 12 > B3 = 10이다.
  • 모든 1 ≤ i, j ≤ N에 대해서 만족하지 않는다.

예제 입력 3

1
2
3
4
5
6
5 3
20 10 30
10 20 60
80 25 79
30 50 80
80 25 81

예제 출력 3

1
2
  • 1번과 5번 우주, 2번과 4번 우주가 균등하다.

힌트


출처


알고리즘 분류


시간 제한


풀이


소스코드

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

input = sys.stdin.readline

M, N = map(int, input().split())

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

new_space_list = [[] for _ in range(M)]
dictionary = {}
for i in range(M):
new_list = sorted(list(set(space_list[i])))
for j in range(len(new_list)):
dictionary[new_list[j]] = j
for x in (space_list[i]):
new_space_list[i].append(dictionary[x])

count = 0
for i in range(M - 1):
for j in range(i + 1, M):
if new_space_list[i] == new_space_list[j]:
count += 1

print(count)