Tag: bruteforcing

n = int(input())
cards = list(map(int, input().split()))

ans = n - 2

# 모든 가능한 두 카드 조합 (i, j)에 대해 확인
for i in range(n):
    for j in range(i + 1, n):
        if (cards[j] - cards[i]) % (j - i) != 0:
            continue
        d = (cards[j] - cards[i]) // (j - i)
        cnt = 0
        
        for k in range(n):
            expected = cards[i] + (k - i) * d
            if cards[k] != expected:
                cnt += 1
        
        ans = min(ans, cnt)

print(ans)

gear1 = list(map(int, list(input().strip())))
gear2 = list(map(int, list(input().strip())))

len1 = len(gear1)
len2 = len(gear2)

if len1 > len2:
    gear1, gear2 = gear2, gear1
    len1, len2 = len2, len1

min_total_length = len1 + len2

for start in range(-len1 + 1, len2):
    
    for i in range(len1):
        gear2_idx = start + i
        if 0 <= gear2_idx < len2:
            # 두 개의 이가 맞물리면 안됨
            if gear1[i] == 2 and gear2[gear2_idx] == 2:
                break

    else:
        current_length = max(len2, start + len1) - min(0, start)
        min_total_length = min(min_total_length, current_length)

print(min_total_length)

from itertools import permutations

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

max_score = 0
# permutations는 애초에 중복 없음 → set() 필요 없음
for perm in permutations([i for i in range(1, 9)]):  # 1번 선수 제외 순열
    order = list(perm[:3]) + [0] + list(perm[3:])  # 0번(1번 선수) 4번 타자 고정

    score = 0
    idx = 0  # 타석 순서 인덱스
    for inning in hit_result:
        out = 0
        base1, base2, base3 = 0, 0, 0  # 각 루의 주자 (0/1)
        while out < 3:
            result = inning[order[idx]]
            if result == 0:
                out += 1
            elif result == 1:
                score += base3
                base1, base2, base3 = 1, base1, base2
            elif result == 2:
                score += base3 + base2
                base1, base2, base3 = 0, 1, base1
            elif result == 3:
                score += base3 + base2 + base1
                base1, base2, base3 = 0, 0, 1
            elif result == 4:
                score += base3 + base2 + base1 + 1
                base1, base2, base3 = 0, 0, 0
            idx = (idx + 1) % 9

    max_score = max(max_score, score)

print(max_score)

첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 주어진다. 단, 2 ≤ N ≤ 30,000, 2 ≤ d ≤ 3,000, 2 ≤ k ≤ 3,000 (k ≤ N), 1 ≤ c ≤ d이다.

주어진 회전 초밥 벨트에서 먹을 수 있는 초밥의 최대 가짓수를 출력하시오.

슬라이딩 윈도우 기법을 사용하는 문제이다.

from collections import defaultdict

N, d, k, c = map(int, input().split())
sushi_list = [int(input()) for _ in range(N)]

counter = defaultdict(int)
kind = 0

for i in range(k):
    if counter[sushi_list[i]] == 0:
        kind += 1
    counter[sushi_list[i]] += 1

# 쿠폰
max_kind = kind + (1 if counter[c] == 0 else 0)

for i in range(1, N):
    remove = sushi_list[i - 1]
    counter[remove] -= 1
    if counter[remove] == 0:  # 더 이상 없으면 종류 수 감소
        kind -= 1

    cur = sushi_list[(i + k - 1) % N]
    if counter[cur] == 0:
        kind += 1
    counter[cur] += 1

    # 쿠폰
    total = kind + (1 if counter[c] == 0 else 0)
    max_kind = max(max_kind, total)  # 최대 종류 수 갱신

print(max_kind)

첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)이 주어진다. 둘째 줄에는 A₁, A₂, …, Aₙ이 주어진다. (1 ≤ Aᵢ ≤ 100) 셋째 줄에는 덧셈, 뺄셈, 곱셈, 나눗셈의 개수가 순서대로 주어진다.

첫째 줄에 만들 수 있는 식의 결과의 최댓값을, 둘째 줄에는 최솟값을 출력한다.

이 문제는 백트래킹을 이용한 브루트포스 문제이다. 가능한 모든 연산자 조합을 시도하여 최대값과 최소값을 찾는다.

1. DFS를 이용하여 모든 연산자 배치 조합을 탐색
2. 각 단계에서 사용 가능한 연산자를 선택하고 계산
3. 모든 수를 사용했을 때 결과를 비교하여 최대/최소 갱신

• 현재 결과값과 사용할 다음 수를 가지고 재귀
• 각 연산자 종류별로 남은 개수가 있으면 시도
• 연산 후 다음 단계로 진행
• 백트래킹: 연산자 개수 복구

operate = ['+', '-', '*','/']

N = int(input())
nums = list(map(int, input().split()))
operator_counter = list(map(int, input().split()))
operator_cnt = sum(operator_counter)

max_com = -float('inf')
min_com = float('inf')


def compute(a, b, op_i):
    if op_i == 0:
        return a + b
    elif op_i == 1:
        return a - b
    elif op_i == 2:
        return a * b
    elif op_i == 3:
        return int(a / b)

def dfs(operator_counter, result, n=0):
    global max_com, min_com
    if n == operator_cnt:
        max_com = max(max_com, result)
        min_com = min(min_com, result)
        return
    for i, cnt in enumerate(operator_counter):
        if cnt == 0:
            continue
        operator_counter[i] -= 1
        dfs(operator_counter, compute(result, nums[n+1], i), n+1)
        operator_counter[i] += 1


dfs(operator_counter, nums[0])

print(max_com)
print(min_com)

• len_limit = min(N - 1, M - 1): 가능한 최대 정사각형의 한 변 길이 (인덱스 차이)
• for k in range(len_limit, -1, -1): 큰 정사각형부터 확인
• for x in range(M - k): 정사각형의 시작 x 좌표 (x + k가 범위를 벗어나지 않도록)
• for y in range(N - k): 정사각형의 시작 y 좌표 (y + k가 범위를 벗어나지 않도록)
• 네 꼭짓점 비교: rectangle[y][x] (좌상), rectangle[y + k][x] (좌하), rectangle[y][x + k] (우상), rectangle[y + k][x + k] (우하)
• break-else 패턴: 조건을 만족하는 정사각형을 찾으면 모든 반복문을 빠져나감

최악의 경우 모든 가능한 정사각형을 확인해야 하므로 시간 복잡도는 O(N × M × min(N, M))이다.

N, M ≤ 50이므로 최악의 경우에도 50 × 50 × 50 = 125,000번의 연산으로 충분히 시간 내에 해결할 수 있다.

max_h = 0
pillar_list = [0] * 1001

max_loc = 0
for _ in range(N):
    loc, h = map(int, input().split())
    max_h = max(max_h, h)
    max_loc = max(max_loc, loc)
    pillar_list[loc] = h

# 왼쪽에서 시작
i_l = -1
cur = 0
ans = 0
while cur < max_h:
    i_l += 1
    cur = max(cur, pillar_list[i_l])
    ans += cur

# 오른쪽에서 시작
i_r = max_loc + 1
cur = 0
while cur < max_h:
    i_r -= 1
    cur = max(cur, pillar_list[i_r])
    ans += cur

if i_r == i_l:
    ans -= max_h
else:
    ans += max_h * (i_r - i_l - 1)

print(ans)

def fill_nemo(d=0):
    global cnt
    if N*M == d:
        cnt += 1
        return
    
    y = d // M + 1
    x = d  % M + 1

    # 사각형이 완성 안되는 경우(넴모를 놓을 수 있는 경우)
    if matrix[y-1][x] == 0 or matrix[y-1][x-1] == 0 or matrix[y][x-1] == 0:
        # 다음 위치에 네모 생성
        matrix[y][x] = 1
        fill_nemo(d+1)
        matrix[y][x] = 0

    # 다음 위치에 네모 생성 X
    fill_nemo(d+1)
    

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

matrix = [[0]*(M+1) for _ in range(N+1)]

cnt = 0
fill_nemo()

print(cnt)

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

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

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