7/19 공부

https://programmers.co.kr/learn/courses/30/lessons/60061?language=python3

코딩테스트 연습 - 기둥과 보 설치

2020년 카카오 신입 공채 문제였다. 물론 나의 레벨보다 한참 높은 문제라 코드 한 줄도 짜지 못했다. 

초보에게 이런 문제는 고민해도 의미가 없기 때문에 바로 답을 보았고 문제 해결접근을 어떻게 하는지,

어떤 식으로 코드를 짜는지만 건져 낸거 같다

 

나동빈님이 제시한 아이디어는 이것이다.

설치나 삭제 연산이 요구 될 때마다 일일이 전체 구조물을 확인하며 규칙을 확인하는 것이다. 

 

다시 문제를 풀 때는 

전체 구조물을 확인하는 함수 possible를 만들 때는 항상

무엇을 체크할 지 설계하고(IF문)해야 된다. 

좋지않은 습관 중 하나 인 무작정 코드를 짜는 걸 고쳐야 한다.

 

또 그림을 그려보고 좌표로 찍어보고 여러가지 case를 만들어 보면서 코드를 짠다면 

문제를 쉽게 접근할 수 있다고 생각한다. 너무 급하게 생각하지 말자

 

 

전체코드

 

#설치및 삭제를 요구할 때마다 일일이 '전체구조물을 확인하며' 규칙을 확인하는 것
#현재 설치된 구조물이 '가능한' 구조물인지 확인하는 함수
def possible(answer):
    for x, y, stuff in answer:
        if stuff == 0: #설치 된 것이 '기둥'인 경우
            #'바닥 위' 혹은 '보의 한쪽 끝부분 위' 혹은 다룬 기둥 위라면 정상
            if y == 0 or [x-1,y,1] in answer or [x,y,1] in answer or [x,y-1,0] in answer:
                continue
            #아니라면 거짓 반환
            return False
        elif stuff == 1: #설치 된 것이 '보'인 경우
            #'한쪽 끝부분이 기둥 위' 혹은 '양쪽 끝부분이 다른 보와 동시에 연결'이라면 정상
            if [x,y-1,0] in answer or [x+1,y-1,0] in answer or ([x-1,y,1] in answer and [x + 1,y,1] in answer)
                continue
            return False #아니라면 거짓 반호나
    return True

def solution(n,build_frame):
    answer = []
    for frame in build_frame: #작업(frame)의 개수는 최대 1000개
    x,y,stuff, operate = frame
    if operate == 0: #삭제하는 경우
        answer.remove([x,y,stuff]) #일단 삭제 해본 다음
        if not possible(answer) #가능한 구조물인지 확인:
            answer.append([x,y,stuff]) #가능한 구조물이 아니라면 다시 설치
    if operate == 1: #설치되는 경우
        answer.append([x,y,stuff]) #일단 설치를 해본 뒤에
        if not possible(answer):
            answer.remove([x,y,stuff]) #가능한 구조물이 아니라면 다시제거
    return sorted(answer)

 

 

https://www.acmicpc.net/problem/15686

15686번: 치킨 배달

이것 또한 내 레벨과 맞지 않아서 못 푼 문제이다. 골드 5임에도 못 푸는 거 보면 코드가 아직 익숙하지 않은 거 같다

푸는 방법은 다음과 같다.

1. m개의 치킨집을 선택하는 조합을 짠다.

2. 그 조합 중 가장 작은 치킨 거리를 가진 조합을 구한다

 

전체코드

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))

#모든 치킨집 중에서 m개의 치킨집을 뽑는 조합 계산
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, getsum(candidate))
print(result)