수학과의 개발자 도전기

-문제: https://www.acmicpc.net/problem/15686

부족했던 점: 

파이썬에서 combinations는 n개에서 m개를 선택한 모든 경우의 수를 구해준다 

치킨거리를 구할 때는 '집'을 기준으로 계산한다 

get_sum()에서 하나의 집 위치 (hx,hy)를 기준으로 각 치킨 집과의 거리를 result에 더한다

from itertools import combinations

n,m=map(int,input().split())
chicken,house=[],[]

for r in range(n):
    data=list(map(int,input().split()))
    for c in range(n):
        if data[c]==1:
            house.append((r,c))
        elif data[c]==2:
            chicken.append((r,c))
            
candidates=list(combinations(chicken,m))

def get_sum(candidate):
    result=0
    for hx,hy in house:
        temp=1e9
        for cx,cy in candidate:
            temp=min(temp,abs(hx-cx)+abs(hy-cy))
        result+=temp
    return result 
        
result=1e9
for candidate in candidates:
    result=min(result,get_sum(candidate))
    
print(result)

-문제: https://www.acmicpc.net/problem/3190

문제 풀면서 부족했던 부분:

방향을 돌리는 turn()함수를 생각해 보지 못한 것 

회전정보를 담고 있는 Info 리스트 생각해보지 못한 것 

꼬리 위치는 q리스트로 파악 가능하다 

백준에서 콛 돌리면서 while 다음 첫번째 If문에서 indexerror가 발생한다. 추후에 고칠 예정

N=int(input())
K=int(input())
board=[[0]*(N+1) for _ in range(N+1)]
for _ in range(K):
    a,b=map(int,input().split())
    board[a][b]=1
    
L=int(input())
info=[]
for _ in range(L):
    x,c=input().split()
    info.append((int(x),c))
dx=[0,1,0,-1]
dy=[1,0,-1,0]

def turn(direction,c):
    if c=='L':
        direction=(direction-1)%4
    else:
        direction=(direction+1)%4
    return direction
        
def simulate():
    x,y=1,1
    board[x][y]=2
    time=0
    direction=0
    index=0
    q=[(x,y)]
    while True:
        nx,ny=x+dx[direction],y+dy[direction]
        if board[nx][ny]!=2 and 1<=nx and nx<=N and 1<=ny and ny<=N:
            if board[nx][ny]==1:
                board[nx][ny]=2
                q.append((nx,ny))
            if board[nx][ny]==0:
                board[nx][ny]=2
                q.append((nx,ny))
                qx,qy=q.pop(0)
                board[qx][qy]=0
        else:
            time+=1
            break
        time+=1
        x,y=nx,ny
    if index<1 and time==info[index][0]:
        direction=turn(direction,info[index][1])
        index+=1
    return time
print(simulate())

문제: https://programmers.co.kr/learn/courses/30/lessons/60059? 

어려웠던 문제다. 어떻게 시작해야할지 감도 안 잡혔던 문제. 

찾아보니 lock보다 3배 큰 행렬을 만들고, 그 중간에 lock 행렬을 넣고 주변에서 key를 움직이면서 값을 더한후 중간 lock행렬의 값이 모두 1일 때 True를 반환하는 방식이었다 

코딩테스트 준비는 정말 쉽지 않은 것 같다 

-정답풀이

def rotate_a_matrix_by_90_degree(a):
	n=len(a)
    m=len(a[0])
    result=[[0]*n for _ in range(m)]
    for i in range(n):
    	for j in range(n):
        	result[j][n-(i+1)]=a[i][j]
	return result
    
    
def check(new_lock):
	lock_length=len(new_lock)//3
    for i in range(lock_length,2*lock_length):
    	for j in range(lock_length,2*lock_length):
        	if new_lock[i][j]!=1:
            	return False	
	return True 
    
    
def solution(key,lock):
	n=len(lock)
    m=len(key)
    new_lock=[[0]*3*n for _ in range(3*n)]
    
    for i in range(n,2*n):
    	for j in range(n,2*n):
        	new_lock[i][j]=lock[i][j]
            
	for rotation in range(4):
    	key=rotate_a_matrix_90_degree(key)
        for x in range(2*n):
        	for y in range(2*n):
            #자물쇠에 열쇠 끼어넣기 
            	for i in range(m):
                	for j in range(m):
                    	new_lock[x+i][y+j]+=key[i][j]
                if check[x][y]!=1:
                	return True
                for i in range(m):
                	for j in range(m):
                    	new_lock[x+i][y+j]-=key[i][j]
                        
	return False