부분합 - BOJ

부분합 - BOJ

• 대표적인 투포인터 문제
• 포인터를 두 개 설정(start, end)하여, end를 한 칸씩 늘려가며 target보다 부분합이 작을 때까지만 부분합을 더하고, target보다 커지면 start를 1칸 올려주는 식으로 구현

N, S = map(int, input().split())
li = list(map(int, input().split()))

end = 0
summary = 0
shortest_len = float('inf')

for s in range(N):
    while summary < S and end < N:
        summary += li[end]
        end += 1
    if summary >= S:
        shortest_len = min(shortest_len, end - s)
    summary -= li[s]

if shortest_len == float('inf'):
    print(0)
else:
    print(shortest_len)

색종이 붙이기 - BOJ

색종이 붙이기 - BOJ

def dfs(x, y, cnt):
    global ret
    if y >= 10:
        ret = min(ret, cnt)
        return
    if x >= 10:
        dfs(0, y + 1, cnt)
        return
    if a[x][y]:
        for p in range(5):
            if paper[p] == 5: # 5개 다 붙였으면 pass
                continue
            if x + p >= 10 or y + p >= 10: # 범위 넘어가면 pass
                continue
            flag = 0
            for i in range(x, x + p + 1):
                for j in range(y, y + p + 1):
                    if not a[i][j]: # 범위가 0이라면
                        flag = 1
                        break
                if flag: break
            if not flag: # 범위에 0이 없다면 (전부 1)
                for i in range(x, x + p + 1):
                    for j in range(y, y + p + 1):
                        a[i][j] = 0

                paper[p] += 1
                dfs(x + p + 1, y, cnt + 1) # 앞뒤로 전부 백트래킹 기법 (최소인 것만 갱신하고 원래 값으로 회복)
                paper[p] -= 1

                for i in range(x, x + p + 1):
                    for j in range(y, y + p + 1):
                        a[i][j] = 1
    else: # 1이 아니면 다음 x
        dfs(x + 1, y, cnt)

a = [list(map(int, input().split())) for _ in range(10)]
paper = [0, 0, 0, 0, 0]
ret = float('inf')
dfs(0, 0, 0)
if ret == float('inf'):
    print(-1)
else:
    print(ret)

배열 B의 값 - BOJ

배열 B의 값 - BOJ

문제 예시의 4X4 배열을 예시로 든다면
0, 1, 2, 3행에서 1,2 행을 바꿔도 최대값이 바뀌지 않을 것임.
따라서 (중간 행 중에서 최소값)과 (0행 or 마지막 행) 중에 행을 하나 교환하거나
열에서도 똑같은 작업을 해서 최대값을 구하면 된다.

def calculate(board):
    _sum = 0
    for i in range(N - 1):
        for j in range(M - 1):
            _sum += board[i][j] + board[i + 1][j] + board[i + 1][j + 1] + board[i][j + 1]
    return _sum

def newmap(x, y, rc): # rc -> r인지 c인지
    b = [[0] * M for _ in range(N)]
    for i in range(N):
        for j in range(M):
            b[i][j] = a[i][j]
    if rc:
        for c in range(M):
            b[x][c], b[y][c] = a[y][c], a[x][c]
    else:
        for r in range(N):
            b[r][x], b[r][y] = a[r][y], a[r][x]
    return b

N, M = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(N)]
row = [0] * N
col = [0] * M
r_min = float('inf')
c_min = float('inf')
min_col, min_row = -1, -1

ret = calculate(a)

# 각 행열 합 계산
for i in range(N):
    for j in range(M):
        row[i] += a[i][j]
        col[j] += a[i][j]

# 최소 크기 행
for r in range(1, N - 1):
    tr = row[r] * 4
    tr -= 2 * (a[r][0] + a[r][M - 1])
    if r_min > tr:
        r_min = tr
        min_row = r

# 최소 크기 열
for c in range(1, M - 1):
    tc = col[c] * 4
    tc -= 2 * (a[0][c] + a[N - 1][c])
    if c_min > tc:
        c_min = tc
        min_col = c

if min_row > 0:
    new = newmap(0, min_row, 1)
    ret = max(ret, calculate(new))
    new = newmap(N - 1, min_row, 1)
    ret = max(ret, calculate(new))

if min_col > 0:
    new = newmap(0, min_col, 0)
    ret = max(ret, calculate(new))
    new = newmap(M - 1, min_col, 0)
    ret = max(ret, calculate(new))

print(ret)

Two Dots - BOJ

Two Dots - BOJ

dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]

def dfs(x, y, cnt):
    global tx, ty, flag
    if flag: return
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if nx < 0 or ny < 0 or nx >= N or ny >= M or a[nx][ny] != a[tx][ty]: # 범위 벗어나지 않고, 색깔이 같을 때만 하도록
            continue
        if not visit[nx][ny]:
            visit[nx][ny] = True # 방문처리 했다가
            dfs(nx, ny, cnt + 1)
            visit[nx][ny] = False # 안한 걸로
        else:
            if cnt >= 4 and tx == nx and ty == ny: # 4번 이상이고 위치가 같을 때 -> 사이클
                flag = True
                return

N, M = map(int, input().split())
a = [list(input()) for _ in range(N)]
visit = [[False] * M for _ in range(N)]
flag = False

for i in range(N):
    for j in range(M):
        if not visit[i][j]:
            tx, ty = i, j
            visit[i][j] = True
            dfs(i, j, 1)
        if flag:
            print("Yes")
            exit(0)

print("No")

적록색약 - BOJ

적록색약 - BOJ

from collections import deque
from copy import deepcopy

dx = [1, -1, 0, 0]
dy = [0, 0, -1, 1]

def a_bfs(i, j):
    cnt = 0
    q1 = deque()
    q1.append((i, j))
    a_visit[i][j] = True
    while q1:
        x, y = q1.popleft()
        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]
            if nx < 0 or ny < 0 or nx >= N  or ny >= N or a_visit[nx][ny]:
                continue
            if a[nx][ny] == a[i][j]:
                a_visit[nx][ny] = True
                q1.append((nx, ny))


def b_bfs(i, j):
    cnt = 0
    q2 = deque()
    q2.append((i, j))
    b_visit[i][j] = True
    while q2:
        x, y = q2.popleft()
        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]
            if nx < 0 or ny < 0 or nx >= N or ny >= N or b_visit[nx][ny]:
                continue
            if b[nx][ny] == b[i][j]:
                b_visit[nx][ny] = True
                q2.append((nx, ny))


N = int(input())
a = [list(input()) for _ in range(N)]
b = deepcopy(a)
for i in range(N):
    for j in range(N):
        if b[i][j] == 'G':
            b[i][j] = 'R'

a_visit = [[False] * N for _ in range(N)]
b_visit = [[False] * N for _ in range(N)]

a_cnt = 0
b_cnt = 0

for i in range(N):
    for j in range(N):
        if not a_visit[i][j]:
            a_bfs(i, j)
            a_cnt += 1
        if not b_visit[i][j]:
            b_bfs(i, j)
            b_cnt += 1

print(a_cnt, b_cnt)