15816, 60057, 3190 (백준)

15686 치킨 배달

📌문제 링크
https://www.acmicpc.net/problem/15686

💡 문제 풀이

• 치킨집을 m개를 고른 후 집마다 가장 가까운 치킨집과의 거리를 계산하여 합의 최솟값을 구한다
• 조합으로 치킨집을 m개 구한 뒤 집마다 치킨집과의 거리를 계산해서 최솟값을 구해주었다.

📋코드

from sys import stdin
from itertools import combinations

input = stdin.readline

n,m = map(int, input().split())
board = []
home = []
chicken = []
for x in range(n):
    board.append(input().strip().split())
    for y in range(n):
        if board[x][y] == '1':
            home.append((x,y))
        elif board[x][y] == '2':
            chicken.append((x,y))

def solv():
    answer = 9e9

    for comb in combinations(chicken,m):
        total = 0
        for sx,sy in home:
            length = 9e9
            for ex,ey in comb:
                length = min(length,abs(sx-ex)+abs(sy-ey))
            total += length
        answer = min(answer,total)

    print(answer)
solv()

60057 프로그래머스 문자열압축

📌문제 링크
https://programmers.co.kr/learn/courses/30/lessons/60057?language=python3

💡 문제 풀이
문제풀이는 주석에 달아 놓았습니다

📋코드

def solution(s):
def cut_str(s):
    length =[]
    result = ""
    
    #길이가 1일 경우 
    if len(s)==1:  
         return 1
    #문자열의 절반까지 자르며 비교     
    for cut in range(1, len(s)//2+1): 
        temp = s[:cut]
        num = 1
        #s의 길이까지 정해진 길이 스텝으로 반복한다
        for i in range(cut, len(s), cut): 
            #다음으로 자른값과 같을경
            if s[i:i+cut] == temp:    우
                num+=1      
            #다를 경우
            else:       
            	#숫자가 1 이면 문자열에 붙지 않으므로 없애줌
                if num == 1:  
                    num=""
                result += str(num)+temp   #결과값에 숫자와 temp에 저장된 값을 저장
                temp = s[i:i+cut]   
                num=1     
        if num == 1:  
            num=""
        result +=str(num)+temp
        length.append(len(temp))
        temp=""
    return min(length) #최소값 반환

3190 뱀

📌문제 링크
https://www.acmicpc.net/problem/3190

💡 문제 풀이

사과는 board에 2로 표시, 뱀의 위치는 1로표시 빈칸은 0으로 표시하였다.

시뮬레이션 함수를 돌아주는데 범위를 벗어나거나 뱀 자기 자신을 만나면 종료한다. 현재 뱀의 방향을 cur_dir 변수에 저장하고 snake_move를 통해 뱀을 이동시켜 주었다.

문제 자체는 시뮬레이션 문제이다. 예제의 입력 값은 맞추었으나 제출했을 때 틀려서 재풀이가 필요하다

📋코드

from collections import deque
import sys
input = sys.stdin.readline

#보드크기, 사과개수
n = int(input())
k = int(input())
board = list([0]*n for _ in range(n) )
# 뱀의 시작 위치
board[0][0] = 1

for _ in range(k):
    y,x = map(int, input().split())
    board[y][x] = 2
l = int(input())
snake_move = deque()

for _ in range(l):
    time, direction = input().split()
    snake_move.append((int(time),direction))

#상우하좌 (시계방향), 현재 방향
move = [(-1,0), (0,1), (1,0), (0,-1)]
cur_dir = 1
# 시간초, 뱀의 머리/꼬리
cnt=0
head = [0,0]
tail = [0,0]
gameover=0

for _ in range(len(snake_move)):
    time, direction = snake_move.popleft()
    while True:


        cnt += 1
        if time==cnt:
            if direction=='L':
                if cur_dir == 0:
                    cur_dir = 3
                else: cur_dir -= 1

            elif direction=='D':
                if cur_dir == 3:
                    cur_dir = 0
                else: cur_dir += 1
            cnt -= 1
            break

        head[0] += move[cur_dir][0]
        head[1] += move[cur_dir][1]

        if not(0 <= head[0] < n) or not(0 <= head[1] < n) or (board[head[0]][head[1]] == 1):
            print(cnt+1)
            gameover = 1
            break
        elif board[head[0]][head[1]] == 2:
            board[head[0]][head[1]] = 1
        
        else: 
            board[head[0]][head[1]] = 1
            board[tail[0]][tail[1]] = 0
        
            tail[0] += move[cur_dir][0]
            tail[1] += move[cur_dir][1]

    if gameover==1:
        break