[백준]230220 문제풀이

14719. 빗물

h, w = map(int, input().split())
blocks = list(map(int, input().split()))
higher = [0] * w
higher[0] = blocks[0]
water = 0

for i in range(1, w):
    # 현재 블록이 이전 블록보다 작을때 상한값을 이전의 상한값까지 올려줌
    if blocks[i] < blocks[i-1]:
        higher[i] = higher[i-1]
    # 현재 블록이 이전 블록보다 클때
    elif blocks[i] >= blocks[i-1]:
        # 현재 블록이 이전 상한값보다 작을 때, 더 큰 블록을 만날때까지 땅을 메꾸고 water 올리기
        if blocks[i] <= higher[i-1]:
            cnt = 1
            while blocks[i] > blocks[i-cnt]:
                water += blocks[i] - blocks[i-cnt]
                blocks[i - cnt] = blocks[i]
                cnt += 1
            higher[i] = higher[i-1]
        # 현재 블록이 이전 상한값보다 클 때, 이전 상한값까지 땅을 메꾸고 water 올리기
        elif blocks[i] > higher[i-1]:
            for j in range(i):
                water += higher[j] - blocks[j]
                blocks[j] = higher[j]
            higher[i] = blocks[i]
print(water)

예전에 풀었던 스택문제랑 비슷한데 계속 안풀려서 엄청 멘붕이 왔다. 블록을 쭉 나열해놓고 이전의 블록과 비교하면서 여태까지의 최대값인 higher를 계속 저장해주면서 진행하다가 블록의 높이가 높아지면 최대값과 높이를 비교해서 각 조건에 맞게 고이는 물을 저장해줬다.

4963. 섬의 개수

import sys
sys.setrecursionlimit(10**6)

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

def dfs(y, x, visitlist):
    for d in range(8):
        if y + dy[d] in range(h) and x + dx[d] in range(w):
            if (y + dy[d], x + dx[d]) not in visitlist and MAP[y + dy[d]][x + dx[d]] == '1':
                visited[y + dy[d]][x + dx[d]] = 1
                visitlist.append((y + dy[d], x + dx[d]))
                dfs(y + dy[d], x + dx[d], visitlist)
            else:
                visited[y + dy[d]][x + dx[d]] = 1
while True:
    w, h = map(int, input().split())
    if w == h == 0:
        break
    MAP = []
    for i in range(h):
        MAP.append(list(map(str, input().split())))
    visited = [[0] * w for _ in range(h)]
    visitlist = []
    cnt = 0
    for y in range(h):
        for x in range(w):
            find = False
            if not visited[y][x] and MAP[y][x] == '1':
                visitlist.append((y, x))
                visited[y][x] = 1
                dfs(y, x, visitlist)
                find = True
            if find:
                cnt += 1
    print(cnt)

분명히 맞게 한 것 같은데 안풀려서 빗물에 이어 멘탈이 와르르 무너진 문제. 심지어 실2인데 왜 틀리는지 감조차 잡지 못하고 있어서 맘고생 좀 했다. 근데 setrecursionlimit을 이용하니 바로 풀릴줄이야... 재귀 말고 다른 방식으로 풀었으면 또 가능했을지 모르겠으나, 이번을 계기로 좀 더 기본부터 차근차근 밟아나가는 연습을 해야겠다 + 알고리즘 분류 안 보고 푸는 연습도

1992. 쿼드트리

N = int(input())
video = []
for i in range(N):
    video.append(str(input()))

def quadtree(lst, n):
    isone = iszero = True
    while isone:
        for i in range(n):
            for j in range(n):
                if lst[i][j] != '1':
                    isone = False
        break
    while iszero:
        for i in range(n):
            for j in range(n):
                if lst[i][j] != '0':
                    iszero = False
        break
    if isone:
        print('1', end = '')
    elif iszero:
        print('0', end = '')
    else:
        lst1 = [lst[i][:n // 2] for i in range(0, n // 2)]
        lst2 = [lst[i][n // 2:] for i in range(0, n // 2)]
        lst3 = [lst[i][:n // 2] for i in range(n // 2, n)]
        lst4 = [lst[i][n // 2:] for i in range(n // 2, n)]
        print('(', end = '')
        quadtree(lst1, n // 2)
        quadtree(lst2, n // 2)
        quadtree(lst3, n // 2)
        quadtree(lst4, n // 2)
        print(')', end = '')

quadtree(video, N)

약간의 노가다가 가미된 문자열 연습문제. 범위랑 괄호 생각만 조금 해주면 바로 풀 수 있다

9935.문자열 폭발

import sys

string = list(map(str, sys.stdin.readline().strip()))
bomb = str(sys.stdin.readline().strip())
stack = []
for i in string:
    stack.append(i)
    while len(stack) >= len(bomb):
        if stack[-len(bomb):] == list(bomb):
            for _ in range(len(bomb)):
                stack.pop()
        else:
            break
if stack:
    print(*stack, sep = '')
else:
    print('FRULA')

확실히 알고리즘 개념에 따른 난이도가 명확하게 드러난다고 느낀 문제. 별다른 테크닉 없이 그냥 풀어도 속임수 없이 답이 바로 나온다. 문자열 최고...

 

전반적으로 3일간 멘탈이 많이 취약해졌는데, 시간은 아직 꽤 있으니 여유롭게 마음 잡고 공부해야겠다.