15686 치킨 배달

문제

조합을 사용하여 최대 M개의 치킨집을 구한뒤, min함수를 사용하여 최솟값을 구하였다.
구현만 하면 되는 문제여서 비효율적이나 반복문을 많이 사용하였다.

# 치킨 배달
import sys
from itertools import combinations

n, m = map(int,sys.stdin.readline().split())
graph = []
for _ in range(n):
    graph.append(list(map(int,sys.stdin.readline().split())))

house = []
chicken = []
for i in range(n):
    for j in range(n):
        if graph[i][j] == 1:
            house.append([i+1,j+1])
        elif graph[i][j] == 2:
            chicken.append([i+1,j+1])

result = 9999
for store in list(combinations(chicken,m)):
    distance = 0
    for j in range(len(house)):
        tmp = 9999
        for k in range(len(store)):
            tmp = min(tmp, abs(house[j][0]-store[k][0]) + abs(house[j][1]-store[k][1]))
        distance += tmp
    result = min(result,distance)

print(result)

3190 뱀

문제
뱀 문제를 보고 처음 든 생각
1) NxN , 90도 회전 -> BFS에서 많이 사용했던 dx,dy 방향 리스트와 범위체크를 활용하면 되겠다.
2) 꼬리 자르기 -> deque을 사용하면 되겠다.
3) 뱀과 사과의 위치 체크 -> 뱀, 사과, 빈 공간에 각각 다른 값을 지정하여 방문처리를 진행하면 되겠다.
이 3가지에 포인트를 두고 문제를 풀었다.

90도 회전 부분
-> 매번 변화하는 방향값을 어떻게 처리해주어야 할지 잘 모르겠어서 이 부분은 구글링을 통해 해결하였다.
=> 나눗셈으로 방향리스트(dx,dy)의 인덱스를 구하는 방식 사용

# 뱀
import sys
from collections import deque

apple = []
time = []
direction = []
n = int(sys.stdin.readline().strip())
k = int(sys.stdin.readline().strip())
graph = [[0] * n for _ in range(n)]
for _ in range(k):
    a,b = map(int,sys.stdin.readline().split())
    graph[a-1][b-1] = 1 # 사과
l = int(sys.stdin.readline().strip())
for _ in range(l):
    tmp = sys.stdin.readline().split()
    time.append(int(tmp[0]))
    direction.append(tmp[1])

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

snake = deque()
snake.append([0,0]) # 꼬리 자르기 체크하기 위함
t = 1
check_direction = 0
x,y = 0, 0
graph[y][x] = 2 # 방문처리

while True:
    x = x + dx[check_direction]
    y = y + dy[check_direction]
    if 0 <= x < n and 0 <= y < n and graph[y][x] != 2:
        if graph[y][x] != 1: # 사과 없으면 꼬리 자르기
            tail_y, tail_x = snake.popleft()
            graph[tail_y][tail_x] = 0  # 꼬리 자르기
        graph[y][x] = 2 # 방문처리
        snake.append([y,x])
        if t in time:
            d = direction[time.index(t)]
            if d == 'D':
                check_direction = (check_direction+1) % 4
            elif d == 'L':
                check_direction = (check_direction-1) % 4
        t += 1 # 1초씩 증가
    else:
        print(t)
        exit()

문자열 압축

문제
"abcabc"
1) [a,b,c,a,b,c]
2) [ab,ca,bc]
3) [abc,abc]
4) [abca,bc]
5) [abcab, c]
6) [abcabc]
이와 같은 과정으로 문자열을 나눠줄 수 있다.
몇가지 경우를 나열해보면 문자열 길이의 절반이상이 되는 경우 즉, "abcabc"의 경우 4부터는 잘린 문자열들의 길이가 달라 문자열 압축이 의미없다는 것을 알 수 있다.
=> 따라서, 문자열 자르기는 len(s)//2+1 까지만 진행하였다.

이후 자른 문자열의 앞뒤를 비교해가며 동일한 문자열이 있을 경우 cnt값을 증가시켜 문자열 압축을 진행하였다.
최종적으로 압축된 문자열 중에 가장 최솟값을 가지는 문자열의 길이를 출력해주었다.

def solution(s):
    if len(s) <= 2:
        return len(s)
    result = []
    for i in range(1,len(s)//2+1): # 문자열을 나눠보면 문자열 길이의 절반이상이 되는 경우는 의미가 없음을 알 수 있음
        tmp = []
        for j in range(0,len(s),i): # 1부터 해당 길이만큼 문자열을 잘라준다.
            tmp.append(s[j:j+i])
        arr = []
        cnt = 1
        for k in range(len(tmp)):
            if k < len(tmp)-1 and tmp[k] == tmp[k+1]:
                cnt += 1
            else:
                if cnt > 1:
                    arr.append(str(cnt) + tmp[k])
                    cnt = 1
                else:
                    arr.append(tmp[k])
            if k == len(tmp)-1:
                result.append(len(''.join(arr)))
    answer = min(result)
    return answer