2020년 9월 28일 월요일

Programmers/코딩테스트 고득점 Kit/동적계획법(Dynamic Programming) 1. N으로 표현.py

문제만 똑바로 읽고 이해했어도 몇시간은 단축시켰을 것이다. 그걸 상기시키려고 올림. 더 효율적인 생각과 코드는 다른사람이 만든 코드를 보자..
from collections import defaultdict
def solution(N, number):
if N == number: return 1
alnd = defaultdict(int)
alnd[N] = 1; alnd[int(str(N)*2)] = 2; alnd[int(str(N)*3)] = 3; alnd[int(str(N)*4)] = 4;
alnd[int(str(N)*5)] = 5; alnd[int(str(N)*6)] = 6; alnd[int(str(N)*7)] = 7; alnd[int(str(N)*8)] = 8;
nl = [[],[N],[int(str(N)*2)],[int(str(N)*3)],[int(str(N)*4)],[int(str(N)*5)],[int(str(N)*6)],[int(str(N)*7)],[int(str(N)*8)]]
result = 9
for i in range(1,9):
for e in nl[i]:
if e==number: return i
for j in range(1,i+1):
if i+j>8:break
for f in nl[j]:
# if not int(str(f) + str(e)) > 32000 and (
# int(str(f) + str(e)) not in alnd or alnd[int(str(f) + str(e))] > i+j):
# nl[i+j].append(int(str(f) + str(e)))
# if int(str(f) + str(e)) in alnd:
# nl[alnd[int(str(f) + str(e))]].remove(int(str(f) + str(e)))
# alnd[int(str(f) + str(e))] = i+j
# if int(str(f) + str(e)) == number:
# if i+j < result: result = i+j
# if not int(str(e) + str(f)) > 32000 and (
# int(str(e) + str(f)) not in alnd or alnd[int(str(e) + str(f))] > i+j):
# nl[i+j].append(int(str(e) + str(f)))
# if int(str(e) + str(f)) in alnd:
# nl[alnd[int(str(e) + str(f))]].remove(int(str(e) + str(f)))
# alnd[int(str(e) + str(f))] = i + j
# if int(str(e) + str(f)) == number:
# if i + j < result: result = i + j
if not e+f > 32000 and (
e+f not in alnd or alnd[e+f] > i+j):
nl[i+j].append(e+f)
if e+f in alnd:
nl[alnd[e+f]].remove(e+f)
alnd[e+f] = i + j
if int(e+f) == number:
if i+j < result: result = i+j
if not e-f < 1 and (
e-f not in alnd or alnd[e-f] > i+j):
nl[i+j].append(e-f)
if e-f in alnd:
nl[alnd[e-f]].remove(e-f)
alnd[e-f] = i + j
if int(e-f) == number:
if i + j < result: result = i + j
if not f-e < 1 and (
f-e not in alnd or alnd[f-e] > i+j):
nl[i+j].append(f-e)
if f-e in alnd:
nl[alnd[f-e]].remove(f-e)
alnd[f-e] = i + j
if int(f-e) == number:
if i + j < result: result = i + j
if not e*f>32000 and (
e*f not in alnd or alnd[e*f] > i+j):
nl[i + j].append(e * f)
if e*f in alnd:
nl[alnd[e*f]].remove(e*f)
alnd[e*f] = i + j
if e*f == number:
if i + j < result: result = i + j
if e // f > 0 and (
e//f not in alnd or alnd[e//f] > i+j):
nl[i + j].append(e // f)
if e//f in alnd:
nl[alnd[e//f]].remove(e//f)
alnd[e//f] = i + j
if e // f == number:
if i + j < result: result = i + j
if f // e > 0 and (
f//e not in alnd or alnd[f//e] > i+j):
nl[i + j].append(f // e)
if f//e in alnd:
nl[alnd[f//e]].remove(f//e)
alnd[f//e] = i + j
if f // e == number:
if i + j < result: result = i + j
# if result < 9:
# return result
# print(*nl,sep='\n')
# print(alnd)
return alnd[number] if number in alnd else -1
print(solution(5,12),4)
print(solution(2,11),3)
print(solution(5,5),1)
print(solution(5,10),2)
print(solution(5,31168),-1)
print(solution(1,1121),7)
print(solution(5,1010),7)
print(solution(3,4),3)
print(solution(5,5555),4)
print(solution(5,5550),5)
print(solution(5,20),3)
print(solution(5,30),3)
print(solution(6,65),4)
print(solution(5,2),3)
print(solution(5,4),3)
print(solution(1,1),1)
print(solution(1,11),2)
print(solution(1,111),3)
print(solution(1,1111),4)
print(solution(1,11111),5)
print(solution(7,7776),6)
print(solution(7,7784),5)
print(solution(2,22222),5)
print(solution(2,22223),7)
print(solution(2,22224),6)
print(solution(2,11111),6)
print(solution(2,11),3)
print(solution(2,111),4)
print(solution(2,1111),5)
print(solution(9,36),4)
print(solution(9,37),6)
print(solution(9,72),3)
print(solution(3,18),3)
print(solution(2,1),2)
print(solution(4,17),4)
'''
5의 경우 할수있는거
1개
5
2개
55, 5+5=10, 5-5=0, 5*5=25, 5/5=1
3개
(55)5, 5(55), 55+5=60, 5+55=60, 55-5=50, -5+55=50, 55*5=275, 5*55=275, 55/5=11, 5/55=0
(10)5, 5(10), 10+5=15, 5+10=15, 10-5=5, -5+10=5, 10*5=50, 5*10=50, 10/5=2, 5/10=0
(0)5, 5(0), 0+5=5, 5+0=5, 0-5=-5, -5+0=-5, 0*5=0, 5*0=0, 0//5=0, 5//0=error
(25)5, 5(25), 25+5=30, 5+25=30, 25-5=20, -5+25=20, 25*5=125, 5*25=125, 25/5=5, 5/25=0
(1)5, 5(1), 1+5=6, 5+1=6, 1-5=-4, -5+1=-4, 1*5=5, 5*1=5, 1/5=0, 5/1=5
'''

2020년 9월 23일 수요일

2020 카카오 인턴십 for Tech developers 문제 / 4. 경주로 건설

https://programmers.co.kr/learn/courses/30/lessons/67259 

미로문제인데 방향까지 고려해서 3차원으로 푼게 인상깊어서 남김.


from collections import deque
def isSafe(y,x,N,board):
return 0<=y<N and 0<=x<N and board[y][x] != 1
def solution(board):
N = len(board)
Q = deque()
# 왼,아래,오,위
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
fd = {2:0 , 3:1, 0:2, 1:3}
dd = {0:"left", 1:"down", 2:"right", 3:"up"}
ds = [[[9999999,9999999,9999999,9999999] for _ in range(N)] for _ in range(N)]
cars = []
ds[0][0][0],ds[0][0][1],ds[0][0][2],ds[0][0][3] = 0,0,0,0
if board[0][1] != 1:
ds[0][1][2] = 100
Q.append((0, 1, 2))
if board[1][0] != 1:
ds[1][0][1] = 100
Q.append((1, 0, 1))
while Q:
# print(Q)
start_y, start_x, dh = Q.popleft()
for i in range(4):
if fd[dh] == i: continue # no go back
new_y = start_y + dy[i]
new_x = start_x + dx[i]
if dh == i: dst = ds[start_y][start_x][dh] + 100
else: dst = ds[start_y][start_x][dh] + 600
if isSafe(new_y, new_x, N, board) and dst <= ds[new_y][new_x][i]:
Q.append((new_y,new_x, i))
ds[new_y][new_x][i] = dst
# print(start_y, start_x, new_y, new_x, dd[i], dst)
# print(*ds, sep='\n')
print(*ds, sep='\n')
return min(ds[N-1][N-1])
# print(solution( [[0, 0, 0], [0, 0, 0], [0, 0, 0]]))
# board = [[0, 0, 1, 0], [0, 0, 0, 0], [0, 1, 0, 1], [1, 0, 0, 0]]
# print(solution([[0, 0, 0], [1, 0, 0], [0, 0, 0]]))
print(solution([[0,0,0,0,0],[0,1,1,1,0],[0,0,1,0,0],[1,0,0,0,1],[0,1,1,0,0]]))

2020년 9월 2일 수요일

10571. 잔디 깎기 D4

막히는 문제 풀다가 푸는 요령을 좀 안것 같아서 씀.

문제의 핵심을 알아내는 것이 중요하다.. 어찌보면 당연하지만
스스로 테스트케이스 여러가지 만들어내면서 정답이 되는 조건을 생각해서 풀어냄. 작은 경우부터 만족시키면서 점점 더 크게..
# 387 ms
import sys

sys.stdin = open("input2.txt", "r")

def is_safe(now_r,now_c):
    now_e = H[now_r][now_c]
    y_bool = True
    x_bool = True

    # 아래 위
    for i in [1,3]:
        new_y = now_r + dy[i]
        new_x = now_c + dx[i]
        while 0 <= new_y < N and 0 <= new_x < M:
            if H[new_y][new_x] > now_e:
                y_bool = False
                break
            new_y += dy[i]
            new_x += dx[i]
        if not(y_bool): break

    # 왼쪽 오른쪽
    for i in [0,2]:
        new_y = now_r + dy[i]
        new_x = now_c + dx[i]
        while 0 <= new_y < N and 0 <= new_x < M:
            if H[new_y][new_x] > now_e:
                x_bool = False
            new_y += dy[i]
            new_x += dx[i]
        if not(x_bool): break

    return y_bool or x_bool

T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
    # ///////////////////////////////////////////////////////////////////////////////////
    N, M = map(int, input().split())

    H = [[0] * M for _ in range(N)]
    for i in range(N):
        H[i] = list(map(int, input().split()))

    # print(*H,sep='\n')

    # 왼쪽, 아래, 오른쪽, 위
    dy = [0, 1, 0, -1]
    dx = [-1, 0, 1, 0]

    result = True
    for r in range(N):
        for c in range(M):
            if not(is_safe(r,c)):
                result = False
        if not(result): break

    result_string = "YES"
    if not(result): result_string = "NO"
    print("#{}".format(test_case), result_string)
    # ///////////////////////////////////////////////////////////////////////////////////
밑에는 핵심 파악 뒤 개선 버전
# 258 ms
import sys

sys.stdin = open("input2.txt", "r")

T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
    # ///////////////////////////////////////////////////////////////////////////////////
    N, M = map(int, input().split())

    Row_max = [0] * N
    H = [[0] * M for _ in range(N)]
    for i in range(N):
        H[i] = list(map(int, input().split()))
        Row_max[i] = max(H[i])

    # print(*H,sep='\n')

    Col_max = [0] * M
    HR = [0 for _ in range(M)]
    for i, c in enumerate(zip(*H)):
        HR[i] = list(c)
        Col_max[i] = max(HR[i])

    # 왼쪽, 아래, 오른쪽, 위
    dy = [0, 1, 0, -1]
    dx = [-1, 0, 1, 0]

    # print(Row_max,Col_max)
    result = True
    for r in range(N):
        for c in range(M):
            if H[r][c] < Row_max[r] and H[r][c] < Col_max[c]:
                result = False
                break
        if not(result): break

    result_string = "YES"
    if not(result): result_string = "NO"
    print("#{}".format(test_case), result_string)
    # ///////////////////////////////////////////////////////////////////////////////////

2020년 9월 1일 화요일

공부용

간단한 지도 표시하기