손가락놀이터

문제후기

1. 문제를 보고 이해하는데 오래걸렸습니다. 문제는 R, G, B 값이 하나씩 주어지는데 이때 앞뒤의 집과 달라야한다는 것과 R, G, B를 그리는데 사용되는 페인트의 양이 최소가 되도록 하는 것입니다. 문제를 보고 DP를 보고 풀면 되겠다고 생각했고 이전에 프로그래머스에서 푼 땅따먹기와 같다고 판단했습니다.
2. R, G, B값과 이전까지 더해진 값의 합을 다시 저장합니다. 이때 이전 위치와 같은 경우는 제외합니다.
3. 마지막 줄에서 가장 최소의 값을 찾습니다.

예시 풀이

문제 예시를 DP를 이용하면 최종적으로 아래의 값이 나온다.

프로그래머스에서 비슷한 문제

문제링크

from sys import stdin

# N 개의 줄
N = int(stdin.readline())

# 배열 RGB값 n개
arr = [list(map(int, stdin.readline().split())) for _ in range(N)]

# 초기 설정값
answer = 1e9

# 1번쨰 줄부터 시작
for n in range(1,N):
    for i in range(3):
        # 미니멈 초기값
        minimum = 1e9
        for j in range(3):
            # 이전과 같은 색인 경우 제외
            # 가장 작은 값 찾기
            if i != j and arr[n][i] + arr[n-1][j] < minimum:
                minimum = arr[n][i] + arr[n-1][j]
        # 가장 작은 값 기록
        arr[n][i] = minimum

print(min(arr[-1]))

문제후기

1. 처음 문제를 보고 BFS를 활용해서 문제를 풀려고 했습니다. 최악의 경우 500 * 500을 BFS로 탐색하는 경우이지만 시간제한이 2초로 애매하지만 통과할 수 있다고 생각하고 코드를 작성했습니다.
2. BFS로 제출한 결과 시간초과에서 걸려서 알고리즘이 틀린 것으로 생각하고 알고리즘을 변경했습니다.
3. 다시 생각해낸 알고리즘은 DP로 최대 Heap과 연관시켜 생각했습니다. 대나무가 많은 순서로 Heap 정렬을 해준 이후 pop을 하면서 메모이제이션을 했습니다. 상하좌우의 메모 중 가장 큰 값 + 1로 메모를 갱신했습니다.
4. Heap에 남은 값이 없으면 모든 메모가 끝났으므로 메모 중에서 가장 큰 값을 출력했습니다.

문제링크

from sys import stdin
import heapq
from itertools import chain

# 상하좌우
dy = [-1,0,1,0]
dx = [0,-1,0,1]

# n 개 매트릭스
n = int(stdin.readline())
# 매트릭스 값 입력
matrix = [list(map(int, stdin.readline().split())) for _ in range(n)]
# 메모이제이션
memoization = [[0] * n for _ in range(n)]
# 최대 힙정렬 할 배열
heap = []

# 최대 힙 정렬
for y in range(n):
    for x in range(n):
        # heapq는 최소힙정렬이므로 -1을 곱해서 최대힙정렬로 한다.
        heapq.heappush(heap, (-1 * matrix[y][x], y, x))


# heap에 값이 없을때까지
while heap:
    _, y, x = heapq.heappop(heap)
    chk_arr = []
    # 상하좌우 체크
    for i in range(4):
        ny = y + dy[i]
        nx = x + dx[i]
        if 0 <= ny < n and 0 <= nx < n:
            # 만약 상,하,좌,우 값이 더 크다면 해당 메모값 배열에 추가
            if matrix[y][x] < matrix[ny][nx]:
                chk_arr.append(memoization[ny][nx])

    if chk_arr: # 만약 배열에 값이 있으면 가장 큰 값 + 1
        memoization[y][x] = max(chk_arr) + 1
    else: # 배열에 값이 없으면 1
        memoization[y][x] = 1
# 메모 중에서 가장 큰 값 출력
print(max(chain(*memoization)))

문제후기

1. 문제를 보고 DP를 활용하는 문제라고 판단했습니다.
2. 계산을 편하게 하기 위해서 좌표와 메트릭스의 크기를 동일하게 하고 계산했습니다.
3. 물 웅덩이가 없는 경우 해당 위치까지 똑같은 크기만큼 이동했기 때문에 비교할 필요 없이 더하면 됩니다.
4. 물 웅덩이가 있는 경우 값을 0으로 만들어 제외했습니다.

문제링크

def solution(m, n, puddles):

    # 매트릭스 제작.
    matrix = [[0] * (m + 1) for _ in range(n + 1)]

    # 출발, 집 좌표
    matrix[1][1] = 1

    # DP 시작
    for y in range(1, n + 1):
        for x in range(1, m + 1):
            # 출발 값
            if y == 1 and x == 1:
                continue
            # 웅덩이가 있는 경우 패쓰
            if [x, y] in puddles:
                matrix[y][x] = 0
            else:
                # 해당 위치 값은 이전값 2개의 합.
                matrix[y][x] = matrix[y - 1][x] + matrix[y][x - 1]

    return matrix[n][m] % 1000000007

문제 리뷰

처음 문제를 보고 단순히 완전탐색을 활용하여 풀려고 했으나 안된다는 것을 알고 방향을 바꿨습니다. DP를 이용하는 것이 가장 좋아보여서 적용 시켜서 풀었습니다.

문제 설명

1와 0로 채워진 표(board)가 있습니다. 표 1칸은 1 x 1 의 정사각형으로 이루어져 있습니다. 표에서 1로 이루어진 가장 큰 정사각형을 찾아 넓이를 return 하는 solution 함수를 완성해 주세요. (단, 정사각형이란 축에 평행한 정사각형을 말합니다.)

예를 들어

가 있다면 가장 큰 정사각형은

가 되며 넓이는 9가 되므로 9를 반환해 주면 됩니다.

제한사항

• 표(board)는 2차원 배열로 주어집니다.
• 표(board)의 행(row)의 크기 : 1,000 이하의 자연수
• 표(board)의 열(column)의 크기 : 1,000 이하의 자연수
• 표(board)의 값은 1또는 0으로만 이루어져 있습니다.

def solution(board):

    if len(board[0]) < 2:
        if [1] in board:
            return 1
        else:
            return 0
    for i in range(1, len(board)):
        for j in range(1, len(board[0])):
            if board[i][j] >= 1:                
                board[i][j] = min(board[i-1][j], board[i][j-1], board[i-1][j-1]) + 1

    return max([num for row in board for num in row]) ** 2