프로그래머스 + BOJ Study 4주차

N으로 표현 - 동적계획법 (Dynamic Programing), Level3

def solution(N, number):

    numbers = [[]] # number[i]는 N을 i개 사용했을 때 나오는 값
    
    for i in range(1, 9):
        temp = {int(str(N) * i)} # NNN...
        for j in range(1, i):
            for number_1 in numbers[j]: # number_1: N을 j개 사용했을 때 나오는 값
                for number_2 in numbers[i - j]: # number_2: N을 (i-j)개 사용했을 때 나오는 값
                    # 즉 number_1과 number_2의 사칙연산을 통한 값은 N을 i개 사용했을 때 나오는 값
                    temp.add(number_1 + number_2)
                    temp.add(number_1 - number_2)
                    temp.add(number_1 * number_2)
                    if number_2 != 0:
                        temp.add(number_1 // number_2)
        numbers.append(temp)
    
    for idx, arr in enumerate(numbers):
        if number in arr:
            return idx
    
    return -1

1. N을 1부터 8까지 사용했을 때 나오는 값들을 저장

    1.1) (N을 i개 사용했을 때 나오는 값) = (N을 j개 사용했을 때 나오는 값) [+ - * //] (N을 i - j개 사용했을 때 나오는 값) (i > j일 때)

2. 1부터 8까지 순서대로 찾고자하는 숫자를 찾을 때 발견하면 index return, 그렇지 않다면 -1 return

 

정수 삼각형 - 동적계획법 (Dynamic Programing), Level3

def solution(triangle):
    
    height = len(triangle)
    
    for i in range(1, height): # 위에서 아래로 진행
        width = len(triangle[i])
        for j in range(width):
            left, right = -1, -1
            if j - 1 >= 0:
                left = triangle[i - 1][j - 1] + triangle[i][j]
            if j < i:
                right = triangle[i - 1][j] + triangle[i][j]
            triangle[i][j] = max(left, right)
    
    return max(triangle[height - 1])

1. 삼각형 꼭대기부터 아래로 진행

2. (현재 위치에서의 최대값) = max(좌측 상단 + 현재값, 우측 상단 + 현재값)

3. 삼각형 가장 아래의 값 중 최대값을 return

 

등굣길 - 동적계획법 (Dynamic Programing), Level3

def solution(m, n, puddles):
    
    # 지역 초기화
    areas = [[0 for _ in range(m)] for _ in range(n)]
    areas[0][0] = 1
    
    # 물에 잠긴 지역
    for puddle_x, puddle_y in puddles:
        areas[puddle_y - 1][puddle_x - 1] = -1
    
    for i in range(n):
        for j in range(m):
            # 물에 잠긴 지역은 경로 계산 X
            if areas[i][j] == -1:
                continue
            
            # 좌측 경로 + 우측 경로 (없다면 제외)로 경로 계산
            # 물에 잠긴 지역(-1)은 제외하여(0) 계산
            if i > 0 and j > 0 and areas[i][j] == 0:
                areas[i][j] = (max(areas[i - 1][j], 0) + max(areas[i][j - 1], 0)) % 1000000007
            elif i > 0 and j == 0:
                areas[i][j] = max(areas[i - 1][j], 0)
            elif i == 0 and j > 0:
                areas[i][j] = max(areas[i][j - 1], 0)
    
    return areas[n - 1][m - 1]

1. 지역에 대한 배열 초기화

    1.1) 지역은 0으로 초기화하고 시작점은 1로 물에 잠긴 지역은 -1로 구성

2. 우측 하단으로 경로를 진행하며 계산

    2.1) (경우의 수) = (좌측 경우의 수) + (상단 경우의 수)

    2.2) 좌측이나 상단이 없는 경우는 좌측과 상단의 경우의 수가 0이라고 가정

    2.3) 좌측이나 상단이 물에 잠긴 지역인 경우 또한 경우의 수가 0이라고 가정

 

BOJ - 14501: 퇴사

import sys

N = int(sys.stdin.readline())   # N: 퇴사까지 남은 날짜
arr = []

for i in range(N):
    T, P = map(int, sys.stdin.readline().split()) # T(i): 걸리는 날짜, P(i): 받는 금액
    arr.append([P, i + T - 1]) # [금액, 상담 종료 날짜]

    temp = 0
    for j in range(i):
        if arr[j][1] < i and temp < arr[j][0]: # 다른 상담의 종료 날짜가 현재 날짜 이전인 경우
            temp = arr[j][0]
    arr[i][0] += temp

answer = 0
for price, end_day in arr:
    if end_day < N and answer < price: # 상담 종료날짜가 퇴사 이전인 경우
        answer = price
print(answer)

1. 현재 날짜를 기준으로 받을 수 있는 최대 금액과 상담 종료 날짜를 기록

    금액 = (현재 날짜를 기준으로 받는 금액) + (현재 날짜보다 이전에 종료되는 가장 많은 금액)

2. 상담 종료 날짜가 퇴사 이전인 경우 최대 금액 return

 

※ 못 푼 문제

1. 사칙연산 - 동적계획법 (Dynamic Programing), Level4

2. 도둑질 - 동적계획법 (Dynamic Programing), Level4

3. BOJ - 9084: 동전

4. BOJ - 2294: 동전2