'브루트포스' 태그의 글 목록

테트로미노

티어 : Gold 5
시간 제한 : 2 초
메모리 제한 : 512 MB
알고리즘 분류 : 구현, 브루트포스 알고리즘

문제

폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다.

정사각형은 서로 겹치면 안 된다.
도형은 모두 연결되어 있어야 한다.
정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다.

정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다.

아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 정수가 하나 쓰여 있다.

테트로미노 하나를 적절히 놓아서 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대로 하는 프로그램을 작성하시오.

테트로미노는 반드시 한 정사각형이 정확히 하나의 칸을 포함하도록 놓아야 하며, 회전이나 대칭을 시켜도 된다.

입력

첫째 줄에 종이의 세로 크기 N과 가로 크기 M이 주어진다. (4 ≤ N, M ≤ 500)

둘째 줄부터 N개의 줄에 종이에 쓰여 있는 수가 주어진다. i번째 줄의 j번째 수는 위에서부터 i번째 칸, 왼쪽에서부터 j번째 칸에 쓰여 있는 수이다. 입력으로 주어지는 수는 1,000을 넘지 않는 자연수이다.

출력

첫째 줄에 테트로미노가 놓인 칸에 쓰인 수들의 합의 최댓값을 출력한다.

예제 입출력

Algorithm

완전 탐색 이용
1. 테트로미노의 모든 경우의 수마다 도느 좌표의 합을 구해 최댓값 갱신
☞ 테트로미노마다 회전과 대칭을 고려해야 함

고려해야 하는 경우의 수가 총 19개
1. 파란색 도형 : 90도 회전
2. 노란색 도형 : 고려할 변형 도형 없음
3. 주황색 도형 : 90도 회전, 180도 회전, 270도 회전, 90도 회전 후 상하대칭, 90도 회전 후 좌우대칭, 상하대칭, 좌우대칭
4. 초록색 도형 : 90도 회전, 90도 회전 후 좌우대칭, 상하대칭
5. 분홍색 도형 : 90도 회전, 180도 회전, 270도 회전

모든 케이스의 반례를 공유해놓은 글이 있어 많은 도움이 되었다.
https://www.acmicpc.net/board/view/61597

Code

import sys
input = sys.stdin.readline

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

max_sum = 0
# 1번 도형 확인
for i in range(N):
    for j in range(M-3):
        if board[i][j] + board[i][j+1] + board[i][j+2] + board[i][j+3] > max_sum:
            max_sum = board[i][j] + board[i][j+1] + board[i][j+2] + board[i][j+3]

# 1번 도형 회전 확인
for i in range(N-3):
    for j in range(M):
        if board[i][j] + board[i+1][j] + board[i+2][j] + board[i+3][j] > max_sum:
            max_sum = board[i][j] + board[i+1][j] + board[i+2][j] + board[i+3][j]

# 2번 도형 확인
for i in range(N-1):
    for j in range(M-1):
        if board[i][j] + board[i][j+1] + board[i+1][j] + board[i+1][j+1] > max_sum:
            max_sum = board[i][j] + board[i][j+1] + board[i+1][j] + board[i+1][j+1]

# 3번 도형, 3번 도형 변형, 4번 도형, 5번 도형 변형 확인
for i in range(N-2):
    for j in range(M-1):
        # 3번 도형
        if board[i][j] + board[i+1][j] + board[i+2][j] + board[i+2][j+1] > max_sum:
            max_sum = board[i][j] + board[i+1][j] + board[i+2][j] + board[i+2][j+1]
        # 3번 도형 180도 회전 도형
        if board[i][j] + board[i][j+1] + board[i+1][j+1] + board[i+2][j+1] > max_sum:
            max_sum = board[i][j] + board[i][j+1] + board[i+1][j+1] + board[i+2][j+1]
        # 3번 도형 오른쪽으로 270도 회전 도형
        if board[i][j] + board[i+1][j] + board[i+2][j] + board[i][j+1] > max_sum:
            max_sum = board[i][j] + board[i+1][j] + board[i+2][j] + board[i][j+1]
        # 3번 도형 좌우 대칭 도형
        if board[i][j+1] + board[i+1][j+1] + board[i+2][j+1] + board[i+2][j] > max_sum:
            max_sum = board[i][j+1] + board[i+1][j+1] + board[i+2][j+1] + board[i+2][j]
        # 4번 도형
        if board[i][j] + board[i+1][j] + board[i+1][j+1] + board[i+2][j+1] > max_sum:
            max_sum = board[i][j] + board[i+1][j] + board[i+1][j+1] + board[i+2][j+1]
        # 4번 도형 상하 대칭 도형
        if board[i][j+1] + board[i+1][j] + board[i+1][j+1] + board[i+2][j] > max_sum:
            max_sum = board[i][j+1] + board[i+1][j] + board[i+1][j+1] + board[i+2][j]
        # 5번 도형 오른쪽으로 90도 회전 도형
        if board[i][j+1] + board[i+1][j] + board[i+1][j+1] + board[i+2][j+1] > max_sum:
            max_sum = board[i][j+1] + board[i+1][j] + board[i+1][j+1] + board[i+2][j+1]
        # 5번 도형 오른쪽으로 270도 회전 도형
        if board[i][j] + board[i+1][j] + board[i+1][j+1] + board[i+2][j] > max_sum:
            max_sum = board[i][j] + board[i+1][j] + board[i+1][j+1] + board[i+2][j]

# 3번 도형 변형, 4번 도형 변형, 5번 도형, 5번 도형 변형 확인
for i in range(N-1):
    for j in range(M-2):
        # 3번 도형 오른쪽으로 90도 회전 도형
        if board[i][j] + board[i+1][j] + board[i][j+1] + board[i][j+2] > max_sum:
            max_sum = board[i][j] + board[i+1][j] + board[i][j+1] + board[i][j+2]
        # 3번 도형 상하 대칭 도형
        if board[i+1][j] + board[i+1][j+1] + board[i+1][j+2] + board[i][j+2] > max_sum:
            max_sum = board[i+1][j] + board[i+1][j+1] + board[i+1][j+2] + board[i][j+2]
        # 3번 도형 오른쪽으로 90도 회전 후 상하 대칭 도형
        if board[i][j] + board[i+1][j] + board[i+1][j+1] + board[i+1][j+2] > max_sum:
            max_sum = board[i][j] + board[i+1][j] + board[i+1][j+1] + board[i+1][j+2]
        # 3번 도형 오른쪽으로 90도 회전 후 좌우 대칭 도형
        if board[i][j] + board[i][j+1] + board[i][j+2] + board[i+1][j+2] > max_sum:
            max_sum = board[i][j] + board[i][j+1] + board[i][j+2] + board[i+1][j+2]
        # 4번 도형 오른쪽으로 90도 회전 도형
        if board[i][j+1] + board[i][j+2] + board[i+1][j] + board[i+1][j+1] > max_sum:
            max_sum = board[i][j+1] + board[i][j+2] + board[i+1][j] + board[i+1][j+1]
        # 4번 도형 오른쪽으로 90도 회전 후 좌우 대칭 도형
        if board[i][j] + board[i][j+1] + board[i+1][j+1] + board[i+1][j+2] > max_sum:
            max_sum = board[i][j] + board[i][j+1] + board[i+1][j+1] + board[i+1][j+2]
        # 5번 도형
        if board[i][j] + board[i][j+1] + board[i][j+2] + board[i+1][j+1] > max_sum:
            max_sum = board[i][j] + board[i][j+1] + board[i][j+2] + board[i+1][j+1]
        # 5번 도형 180도 회전 도형
        if board[i][j+1] + board[i+1][j] + board[i+1][j+1] + board[i+1][j+2] > max_sum:
            max_sum = board[i][j+1] + board[i+1][j] + board[i+1][j+1] + board[i+1][j+2]

print(max_sum)

메모리: 36024 KB
시간: 1720 ms

저작자표시 비영리 변경금지

'백준 > Python' 카테고리의 다른 글

[백준 3190] 뱀 Python (0)	2022.03.31
[백준 12904] A와 B Python (0)	2022.03.31
[백준 1107] 리모컨 Python (0)	2022.03.30
[백준 1475] 날짜 계산 Python (0)	2022.03.30
[백준 3085] 사탕 게임 Python (0)	2022.03.30

리모컨

티어 : Gold 5
시간 제한 : 2 초
메모리 제한 : 256 MB
알고리즘 분류 : 브루트포스 알고리즘

문제

수빈이는 TV를 보고 있다. 수빈이는 채널을 돌리려고 했지만, 버튼을 너무 세게 누르는 바람에, 일부 숫자 버튼이 고장났다.

리모컨에는 버튼이 0부터 9까지 숫자, +와 -가 있다. +를 누르면 현재 보고있는 채널에서 +1된 채널로 이동하고, -를 누르면 -1된 채널로 이동한다. 채널 0에서 -를 누른 경우에는 채널이 변하지 않고, 채널은 무한대 만큼 있다.

수빈이가 지금 이동하려고 하는 채널은 N이다. 어떤 버튼이 고장났는지 주어졌을 때, 채널 N으로 이동하기 위해서 버튼을 최소 몇 번 눌러야하는지 구하는 프로그램을 작성하시오.

수빈이가 지금 보고 있는 채널은 100번이다.

입력

첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼이 주어지며, 같은 버튼이 여러 번 주어지는 경우는 없다.

출력

첫째 줄에 채널 N으로 이동하기 위해 버튼을 최소 몇 번 눌러야 하는지를 출력한다.

예제 입출력

힌트

예제 1의 경우 5455++ 또는 5459--

Algorithm

완전 탐색 이용
1. 고장난 버튼을 제거하고 찾는 채널과 가장 가까운 수 만들기
2. 해당 숫자의 자리수 + (찾는 채널 - 만든 수) Return

고려해야 할 조건들이 너무 많아 힘들었던 문제 ㅠㅠ

Code

import sys
input = sys.stdin.readline

N = int(input())
M = int(input())
error_key = []
if M > 0:
    error_key = list(map(int, input().split()))
# 사용 가능한 키는 True, 그렇지 않으면 False
error_keys = dict()
for i in range(10):
    if i not in error_key:
        error_keys[i] = True
    else:
        error_keys[i] = False

# 보고싶은 채널과 가장 가까운 숫자 만들기
one_step = 5000011
# 찾는 채널보다 작은 수로 가까운 숫자 만들기
for num in range(N, -1, -1):
    # 찾는 채널이 100이거나 M이 0이거나 숫자가 모두 고장이면 break
    if N == 100 or M == 0 or M == 10:
        break
    
    # keys 중 error_key에 없는 숫자를 이용해 해당 숫자 만들 수 있으면 break
    temp = list(str(num))
    # error_key가 아닌 key 개수 세기
    count = 0
    for i in temp:
        if error_keys[int(i)]:
            count += 1
    # count가 temp의 길이와 같으면 만들 수 있는 숫자
    if count == len(temp):
        one_step = num
        break

# 찾는 채널보다 큰 수로 가까운 숫자 만들기
num = N
while True:
    # 찾는 채널이 100이거나 M이 0이거나 숫자가 모두 고장이면 break
    if N == 100 or M == 0 or M == 10:
        break
    
    # keys 중 error_key에 없는 숫자를 이용해 해당 숫자 만들 수 있으면 break
    temp = list(str(num))
    # error_key가 아닌 key 개수 세기
    count = 0
    for i in temp:
        if error_keys[int(i)]:
            count += 1
    # count가 temp의 길이와 같으면 만들 수 있는 숫자
    if count == len(temp):
        # 찾는 채널보다 작은 채널의 숫자 차이가 작으면 갱신
        if one_step < N:
            if N - one_step > num - N:
                one_step = num
                break
        else:
            one_step = num
            break
    
    if one_step < N and num - N >= N - one_step:
        break
    num += 1

answer = 0
if N != 100:
    if M == 10 or one_step == 5000011:
        if M == 0:
            answer = min(max(100-N, N-100), len(str(N)))
        else:
            answer = max(N - 100, 100-N)
    # 100에서 +와 -만을 이용해 움직인 횟수가 one_step과의 차이보다 작으면 갱신
    elif max(100-N, N-100) < max(N-one_step, one_step-N) + len(str(N)):
        if one_step == 5000011:
            answer = min(max(100-N, N-100), len(str(N)))
        else:
            answer = max(100-N, N-100)
    # 숫자 중 고장난 키가 하나도 없으면 채널 번호 길이만큼 출력
    elif M == 0:
        answer = len(str(N))
    else:
        answer = len(str(one_step))
        answer += max(N - one_step, one_step - N)
print(str(answer))

메모리: 30864 KB
시간: 2004 ms

저작자표시 비영리 변경금지

'백준 > Python' 카테고리의 다른 글

[백준 12904] A와 B Python (0)	2022.03.31
[백준 14500] 테트로미노 Python (0)	2022.03.31
[백준 1475] 날짜 계산 Python (0)	2022.03.30
[백준 3085] 사탕 게임 Python (0)	2022.03.30
[백준 2309] 일곱 난쟁이 Python (0)	2022.03.24

날짜 계산

티어 : Silver 5
시간 제한 : 2 초
메모리 제한 : 4 MB
알고리즘 분류 : 수학, 브루트포스 알고리즘, 정수론, 중국인의 나머지 정리

문제

준규가 사는 나라는 우리가 사용하는 연도와 다른 방식을 이용한다. 준규가 사는 나라에서는 수 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이기 때문에, 정답이 음수가 나오는 경우는 없다.

예제 입출력

Algorithm

1. 현재 시간 1 증가
2. e, s, m 1 증가
☞ 각각 15, 28, 19를 넘으면 1로 초기화

Code

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

e, s, m = 0, 0, 0
time = 0
while True:
    time += 1
    
    if e == 15:
        e = 1
    else:
        e += 1
        
    if s == 28:
        s = 1
    else:
        s += 1
        
    if m == 19:
        m = 1
    else:
        m += 1
        
    if e == E and s == S and m == M:
        break

print(time)

메모리: 30860 KB
시간: 72 ms

저작자표시 비영리 변경금지

'백준 > Python' 카테고리의 다른 글

[백준 14500] 테트로미노 Python (0)	2022.03.31
[백준 1107] 리모컨 Python (0)	2022.03.30
[백준 3085] 사탕 게임 Python (0)	2022.03.30
[백준 2309] 일곱 난쟁이 Python (0)	2022.03.24
[백준 6588] 골드바흐의 추측 Python (0)	2022.03.24

사탕 게임

티어 : Silver 3
시간 제한 : 1 초
메모리 제한 : 128 MB
알고리즘 분류 : 구현, 브루트포스 알고리즘

문제

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

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

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

입력

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

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

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

출력

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

예제 입출력

힌트

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

Algorithm

1. 사탕의 색상을 2차원 리스트 board에 저장
2. board를 하나씩 확인하면서 행에 같은 사탕이 몇 개인지 세기
2.1. 행: board[i][j]부터 board[i][j+1]까지 같은 색이면 count + 1
다른 색이면 count 1로 초기화하고 continue
2.2. 열: board[i][j]부터 board[i+1][j]까지 같은 색이면 count + 1
다른 색이면 count 1로 초기화하고 continue
3. board를 하나씩 확인하면서 열에 같은 사탕이 몇 개인지 세기
3.1. 행: board[i][j]부터 board[i][j+1]까지 같은 색이면 count + 1
다른 색이면 count 1로 초기화하고 continue
3.2. 열: board[i][j]부터 board[i+1][j]까지 같은 색이면 count + 1
다른 색이면 count 1로 초기화하고 continue

Code

import sys
input = sys.stdin.readline

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

# 행을 기준으로 다른 색상 교환
max_count = 1
for i in range(N):
    for j in range(N-1):
        # 인접한 행의 색상이 다르면 교환
        if board[i][j] != board[i][j+1]:
            board[i][j], board[i][j+1] = board[i][j+1], board[i][j]
            
            # 교환했을 때 사탕의 최대 개수 체크
            
            # 행 확인
            for x in range(N):
                count = 1
                for y in range(N-1):
                    # 인접한 행의 색상이 같으면 count 증가
                    if board[x][y] == board[x][y+1]:
                        count += 1
                        
                    else: # 같지 않으면 count 1로 초기화하고 다음 칸 확인
                        if max_count < count:
                            max_count = count
                        count = 1
                        continue
                    
                    if max_count < count:
                        max_count = count
                        
            # 열 확인
            for y in range(N):
                count = 1
                for x in range(N-1):
                    # 인접한 열의 색상이 같으면 count 증가
                    if board[x][y] == board[x+1][y]:
                        count += 1
                        
                    else: # 같지 않으면 count 1로 초기화하고 다음 칸 확인
                        if max_count < count:
                            max_count = count
                        count = 1
                        continue
                    
                    if max_count < count:
                        max_count = count
                    
            # 교환했던 칸 원위치
            board[i][j], board[i][j+1] = board[i][j+1], board[i][j]

# 열을 기준으로 다른 색상 교환
for j in range(N):
    for i in range(N-1):
    
        # 인접한 열의 색상이 다르면 교환
        if board[i][j] != board[i+1][j]:
            board[i][j], board[i+1][j] = board[i+1][j], board[i][j]

            # 교환했을 때 사탕의 최대 개수 체크
            # 행 확인
            for x in range(N):
                count = 1
                for y in range(N-1):
                    # 인접한 행의 색상이 같으면 count 증가
                    if board[x][y] == board[x][y+1]:
                        count += 1
                        
                    else: # 같지 않으면 count 1로 초기화하고 다음 칸 확인
                        if max_count < count:
                            max_count = count
                        count = 1
                        continue
                    
                    if max_count < count:
                        max_count = count
            
            # 열 확인
            for y in range(N):
                count = 1
                for x in range(N-1):
                    # 인접한 열의 색상이 같으면 count 증가
                    if board[x][y] == board[x+1][y]:
                        count += 1
                    else: # 같지 않으면 count 1로 초기화하고 다음 칸 확인
                        if max_count < count:
                            max_count = count
                        count = 1
                        continue
                    
                    if max_count < count:
                        max_count = count
                    
            # 교환했던 칸 원위치
            board[i][j], board[i+1][j] = board[i+1][j], board[i][j]

print(max_count)

메모리: 30864 KB
시간: 4296 ms

저작자표시 비영리 변경금지

'백준 > Python' 카테고리의 다른 글

[백준 1107] 리모컨 Python (0)	2022.03.30
[백준 1475] 날짜 계산 Python (0)	2022.03.30
[백준 2309] 일곱 난쟁이 Python (0)	2022.03.24
[백준 6588] 골드바흐의 추측 Python (0)	2022.03.24
[백준 1929] 소수 구하기 Python (0)	2022.03.24

체스판 다시 칠하기

티어 : Silver 5
시간 제한 : 2 초
메모리 제한 : 128 MB
알고리즘 분류 : 브루트포스 알고리즘

문제

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

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

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

입력

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

출력

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

예제 입출력

Algorithm

1. 리스트에 string형트로 저장
2. 보드 잘라내기
-> 시작좌표 주면 거기서부터 8*8에 해당하는 곳에서 색칠을 다시 해야하는 칸 갯수 반환하는 함수 구현
3. 왼쪽 맨 위가 흰색이라고 가정
3.1. 이중 for문을 돌면서 흰-검-흰-검-... 순서가 맞는지 확인
3.2. i 값이 바뀔 때마다 흰색과 검정의 순서 변경
4. 왼쪽 맨 위가 검은색이라고 가정
4.1. 이중 for문을 돌면서 검-흰-검-흰-... 순서가 맞는지 확인
4.2. i 값이 바뀔 때마다 흰색과 검정의 순서 변경
5. 2번과 3번 과정 중 최솟값 출력

Code

def count_func(x, y):
    
    if x < 0 or x > N - 8 or y < 0 or y > M - 8:
        return False
    
    now = ['W', 'B']
    count = [0] * 2 # 다시 칠해야 하는 칸의 수를 셀 리스트
    
    # 왼쪽 맨 위가 흰색이라고 가정
    for i in range(x, x + 8):
        for j in range(y, y + 8):
            
            if i % 2 == 0: # 짝수행일 때
                if j % 2 == 0: # 짝수열이면
                    index = 0 # 흰색
                else: # 홀수열이면
                    index = 1 # 검은색
                    
            else: # 홀수 행일 때
                if j % 2 == 0: # 짝수열이면
                    index = 1 # 검은색
                else: # 홀수열이면
                    index = 0 # 흰색
            
            # 원래 있어야 하는 색과 칠해져있는 색이 같지 않으면 count += 1
            if graph[i][j] != now[index]:
                count[0] += 1
    
    # 왼쪽 맨 위가 검은색이라고 가정
    for i in range(x, x + 8):
        for j in range(y, y + 8):
            
            if i % 2 == 0: # 짝수행일 때
                if j % 2 == 0: # 짝수열이면
                    index = 1 # 검은색
                else: # 홀수열이면
                    index = 0 # 흰색
                    
            else: # 홀수 행일 때
                if j % 2 == 0: # 짝수열이면
                    index = 0 # 흰색
                else: # 홀수열이면
                    index = 1 # 검은색
                    
            # 원래 있어야 하는 색과 칠해져있는 색이 같지 않으면 count += 1
            if graph[i][j] != now[index]:
                count[1] += 1
                
    return count

# 입력
N, M = map(int, input().split())
graph = []
for _ in range(N):
    graph.append(input())

min_ = M*N
for i in range(N):
    for j in range(M):

        temp = []
        temp = count_func(i, j)
        
        # 위의 함수를 돌고 나왔을 때 False가 아니라면
        if temp:
            # 최솟값 갱신
            min_ = min(min_, temp[0], temp[1])

print(min_)

메모리: 30864 KB
시간: 124 ms

저작자표시 비영리 변경금지

'백준 > Python' 카테고리의 다른 글

[백준 3036] 링 Python (0)	2022.03.05
[백준 2609] 최대공약수와 최소공배수 Python (0)	2022.03.05
[백준 1012] 유기농 배추 Python (0)	2022.03.05
[백준 1008] A/B Python (0)	2022.03.05
[백준 5086] 배수와 약수 Python (0)	2022.03.05

영화감독 숌

티어 : Silver 5
시간 제한 : 2 초
메모리 제한 : 128 MB
알고리즘 분류 : 브루트포스 알고리즘

문제

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번째 영화의 제목에 들어간 수를 출력한다.

예제 입출력

Algorithm

1. for문을 돌면서 6이 3번 연속으로 들어가는 숫자 찾을 때마다 count
2. count == N일 때 해당 숫자 출력

Code

# 입력
N = int(input())

num = 666
frequency = 1 # 666이 들어가는 숫자가 나온 횟수 count
while True:
    # 첫 번째 숫자일 때는 while문 돌지 않고 빠져나감
    if N == 1:
        break
    
    # 숫자를 하나씩 증가시키면서 6이 연속으로 세 번 들어가는 숫자가 나오는지 확인
    num += 1
    temp = str(num)
    
    count = 0
    if '666' in temp:
        frequency += 1
        
    if frequency == N:
        break

print(num)

메모리: 30864 KB
시간: 1004 ms

저작자표시 비영리 변경금지

'백준 > Python' 카테고리의 다른 글

[백준 11650] 좌표 정렬하기 (0)	2022.03.03
[백준 2108] 통계학 Python (0)	2022.03.03
[백준 1018] 체스판 다시 칠하기 Python (0)	2022.03.03
[백준 7568] 덩치 Python (0)	2022.03.03
[백준 2525] 오븐 시계 Python (0)	2022.03.03

체스판 다시 칠하기

티어 : Silver 5
시간 제한 : 2 초
메모리 제한 : 128 MB
알고리즘 분류 : 브루트포스 알고리즘

문제

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

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

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

입력

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

출력

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

예제 입출력

Algorithm

1. 리스트에 string형트로 저장
2. 보드 잘라내기
-> 시작좌표 주면 거기서부터 8*8에 해당하는 곳에서 색칠을 다시 해야하는 칸 갯수 반환하는 함수 구현
3. 왼쪽 맨 위가 흰색이라고 가정
3.1. 이중 for문을 돌면서 흰-검-흰-검-... 순서가 맞는지 확인
3.2. i 값이 바뀔 때마다 흰색과 검정의 순서 변경
4. 왼쪽 맨 위가 검은색이라고 가정
4.1. 이중 for문을 돌면서 검-흰-검-흰-... 순서가 맞는지 확인
4.2. i 값이 바뀔 때마다 흰색과 검정의 순서 변경
5. 2번과 3번 과정 중 최솟값 출력

Code

def count_func(x, y):
    
    if x < 0 or x > N - 8 or y < 0 or y > M - 8:
        return False
    
    now = ['W', 'B']
    count = [0] * 2 # 다시 칠해야 하는 칸의 수를 셀 리스트
    
    # 왼쪽 맨 위가 흰색이라고 가정
    for i in range(x, x + 8):
        for j in range(y, y + 8):
            
            if i % 2 == 0: # 짝수행일 때
                if j % 2 == 0: # 짝수열이면
                    index = 0 # 흰색
                else: # 홀수열이면
                    index = 1 # 검은색
                    
            else: # 홀수 행일 때
                if j % 2 == 0: # 짝수열이면
                    index = 1 # 검은색
                else: # 홀수열이면
                    index = 0 # 흰색
            
            # 원래 있어야 하는 색과 칠해져있는 색이 같지 않으면 count += 1
            if graph[i][j] != now[index]:
                count[0] += 1
    
    # 왼쪽 맨 위가 검은색이라고 가정
    for i in range(x, x + 8):
        for j in range(y, y + 8):
            
            if i % 2 == 0: # 짝수행일 때
                if j % 2 == 0: # 짝수열이면
                    index = 1 # 검은색
                else: # 홀수열이면
                    index = 0 # 흰색
                    
            else: # 홀수 행일 때
                if j % 2 == 0: # 짝수열이면
                    index = 0 # 흰색
                else: # 홀수열이면
                    index = 1 # 검은색
                    
            # 원래 있어야 하는 색과 칠해져있는 색이 같지 않으면 count += 1
            if graph[i][j] != now[index]:
                count[1] += 1
                
    return count

# 입력
N, M = map(int, input().split())
graph = []
for _ in range(N):
    graph.append(input())

min_ = M*N
for i in range(N):
    for j in range(M):

        temp = []
        temp = count_func(i, j)
        
        # 위의 함수를 돌고 나왔을 때 False가 아니라면
        if temp:
            # 최솟값 갱신
            min_ = min(min_, temp[0], temp[1])

print(min_)

메모리: 30864 KB
시간: 124 ms

저작자표시 비영리 변경금지

'백준 > Python' 카테고리의 다른 글

[백준 2108] 통계학 Python (0)	2022.03.03
[백준 1436] 영화감독 숌 Python (0)	2022.03.03
[백준 7568] 덩치 Python (0)	2022.03.03
[백준 2525] 오븐 시계 Python (0)	2022.03.03
[백준 2480] 주사위 세개 Python (0)	2022.03.03

덩치

N명의 집단에서 각 사람의 덩치 등수는 자신보다 더 "큰 덩치"의 사람의 수로 정해진다. 만일 자신보다 더 큰 덩치의 사람이 k명이라면 그 사람의 덩치 등수는 k+1이 된다. 이렇게 등수를 결정하면 같은 덩치 등수를 가진 사람은 여러 명도 가능하다. 아래는 5명으로 이루어진 집단에서 각 사람의 덩치와 그 등수가 표시된 표이다.

티어 : Silver 5
시간 제한 : 1 초
메모리 제한 : 128 MB
알고리즘 분류 : 구현, 브루트포스 알고리즘

문제

우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시된다. 두 사람 A 와 B의 덩치가 각각 (x, y), (p, q)라고 할 때 x > p 그리고 y > q 이라면 우리는 A의 덩치가 B의 덩치보다 "더 크다"고 말한다. 예를 들어 어떤 A, B 두 사람의 덩치가 각각 (56, 177), (45, 165) 라고 한다면 A의 덩치가 B보다 큰 셈이 된다. 그런데 서로 다른 덩치끼리 크기를 정할 수 없는 경우도 있다. 예를 들어 두 사람 C와 D의 덩치가 각각 (45, 181), (55, 173)이라면 몸무게는 D가 C보다 더 무겁고, 키는 C가 더 크므로, "덩치"로만 볼 때 C와 D는 누구도 상대방보다 더 크다고 말할 수 없다.

위 표에서 C보다 더 큰 덩치의 사람이 없으므로 C는 1등이 된다. 그리고 A, B, D 각각의 덩치보다 큰 사람은 C뿐이므로 이들은 모두 2등이 된다. 그리고 E보다 큰 덩치는 A, B, C, D 이렇게 4명이므로 E의 덩치는 5등이 된다. 위 경우에 3등과 4등은 존재하지 않는다. 여러분은 학생 N명의 몸무게와 키가 담긴 입력을 읽어서 각 사람의 덩치 등수를 계산하여 출력해야 한다.

입력

첫 줄에는 전체 사람의 수 N이 주어진다. 그리고 이어지는 N개의 줄에는 각 사람의 몸무게와 키를 나타내는 양의 정수 x와 y가 하나의 공백을 두고 각각 나타난다.

출력

여러분은 입력에 나열된 사람의 덩치 등수를 구해서 그 순서대로 첫 줄에 출력해야 한다. 단, 각 덩치 등수는 공백문자로 분리되어야 한다.

제한

2 ≤ N ≤ 50
10 ≤ x, y ≤ 200

예제 입출력

Algorithm

1. 리스트에 튜플 형태로 입력
2. 이중 FOR문 돌면서 자신보다 덩치가 큰 사람 수 COUNT해 새로운 리스트에 저장

Code

# 입력
N = int(input())
datas = []
for _ in range(N):
    datas.append(tuple(map(int, input().split())))
    
# 자신보다 덩치가 큰 사람 수 count
count = [0] * N # 덩치 큰 사람의 수를 저장할 리스트
for i in range(N):
    for j in range(N):
        if datas[i][0] < datas[j][0] and datas[i][1] < datas[j][1]:
            # 덩치가 큰 사람이 있으면 count에 추가
            count[i] += 1
            
for i in count:
    print(i+1, end = ' ')

메모리: 30860 KB
시간: 72 ms

저작자표시 비영리 변경금지

'백준 > Python' 카테고리의 다른 글

[백준 2108] 통계학 Python (0)	2022.03.03
[백준 1436] 영화감독 숌 Python (0)	2022.03.03
[백준 1018] 체스판 다시 칠하기 Python (0)	2022.03.03
[백준 2525] 오븐 시계 Python (0)	2022.03.03
[백준 2480] 주사위 세개 Python (0)	2022.03.03