코드업 문제 풀이

[시뮬레이션]

 

6098: [기초-리스트] 성실한 개미

# 0: 갈수있는 곳 1: 벽 2: 먹이
# 계속 오른쪽으로만 가는데 벽이 있으면 한칸 아래로 감

maze = []
x, y = 1, 1
for i in range(10):
  maze.append(list(map(int, input().split())))

dx = (0, 1)
dy = (1, 0)
turn_count = 0

# 첫 위치는 방문처리
maze[x][y] = 9

while True:
  # 회전을 두번 했다면 종료
  if turn_count >= 2:
    break
  
  # 이동할 곳이 벽이 아니라면
  if maze[x+dx[turn_count]][y+dy[turn_count]] == 0:
    x = x + dx[turn_count]
    y = y + dy[turn_count]
    maze[x][y] = 9
    turn_count = 0
  # 이동할 곳이 벽이라면
  elif maze[x+dx[turn_count]][y+dy[turn_count]] == 1:
    turn_count += 1
  # 그 외의 경우는 먹이를 발견했을 때
  else:
    x = x + dx[turn_count]
    y = y + dy[turn_count]
    maze[x][y] = 9
    break

for i in range(10):
  for j in range(10):
    print(maze[i][j], end=' ')
  print("")

 

 

[그리디]

 

3120: 리모컨

a, b = map(int, input().split())
target = abs(a - b)

# 먼저 10으로 나눠준다
result = target // 10
target = target % 10


if target in [1, 5]: # 1: +1 / 5: +5
  result += 1
elif target in [2, 4, 6, 9]: # 2: +1,+1 / 4: 5,-1 / 6: 5,+1 / 9: +10,-1
  result += 2
elif target in [3, 7, 8]: # 3: +1,+1,+1 / 7: +5,+1,+1 / 8: +10,-1,-1
  result += 3

print(result)

쓸데없이 생각을 너무 복잡하고 길게 하는것 같다. 최적해를 찾기 위해 생각을 단순화 시킬 필요가 있다

고작 이거하나 짜는데 1시간이 걸렸다

 

3321: 최고의 피자

t = int(input())
dPrice, tPrice = map(int, input().split())
dCalorie = int(input())

tCalorie = []
for i in range(t):
  tCalorie.append(int(input()))
  
# cpd의 효율을 위해 내림차순 정렬
tCalorie.sort(reverse=True)

totalCalorie = dCalorie
totalPrice = dPrice
cpd = totalCalorie // totalPrice # calorie per dollar

for x in tCalorie:
  # 토핑의 cpd가 전체 cpd보다 높으면 토핑 추가
  if (x // tPrice) > cpd:
    totalCalorie += x
    totalPrice += tPrice
    cpd = totalCalorie // totalPrice
  # 오름차순 정렬이기때문에 한번만 만족하지 못해도 루프 탈출
  else:
    break

print(format(cpd,".0f"))

접근은 거의 다 했는데 누적 평균값을 고려하지 않아서 조금 헤맸음

 

4040: 펜션

from sys import stdin

period, r = map(int, stdin.readline().split())

schedule = [0] * period

for i in range(0, period):
  schedule[i] = (list(map(str, stdin.readline().rstrip())))

start, end = map(int, stdin.readline().split())
start -= 1 # 인덱스 접근을 편하게 하기위해 감소
end -= 1
changeCount = -1

while start < end:
  maxDay = 0
  
  for i in range(r):
    count = 0
    for j in range(start, end):
      # 빈방을 발견하면 계속 확인함
      if schedule[j][i] in 'O':
        count += 1
      else:
        break
    # 최대 숙박 가능일
    if maxDay < count:
      maxDay = count

  # 숙박 가능일이 0이 아니면 방이 있음
  if maxDay != 0:
    start += maxDay
    changeCount += 1
  # 숙박 가능일이 0이면 예약이 다 찬상태
  else:
    changeCount = -1
    break

print(changeCount)

시간초과가 계속 뜨길래 입력방법도 바꿔보고 했다가 뒤늦게 안 사실은 마지막에 break 하나를 안넣어서 루프탈출을 못해서 그런거였다. 그걸 못찾고 계속 코드 다듬다가 30분이 갔다

이번에는 충분히 할 수 있는데도 '이 방법은 아니지 않을까?' 하면서 고민을 너무 오래했다

최대 숙박 가능일들을 뽑아서 방 번호와 튜플로 묶어서 리스트에 보관하는 뻘짓을 했었는데 조금 생각해보니 그런 데이터를 보관할 필요가 없다는걸 깨닫고 다 날려버림

 

4713: 공주님의 정원

# [0]시작월 [1]시작일 [2]종료월 [3]종료일

# 3/1 ~ 11/30
# 1. 시작일(초기3/1) 이하 꽃중에 가장 늦게까지 피는 꽃 선택
# 2. 해당 꽃 종료일 이하 꽃중에 현재 종료일보다 더 뒤쪽으로 가장 늦게까지 피는 꽃 선택
# 만약 선택할 수 없다면 0 반환후 즉시 종료
# 매 선택마다 11/30이 초과되는지 확인해야한다
# 선택된 꽃 카운팅 해서 출력

n = int(input())

array = [0] * n
for i in range(n):
  array[i] = list(map(int, input().split()))

# 시작월일 기준으로 정렬
array.sort(key = lambda x: (x[0], x[1]))

index, result = 0, 0
start = [3, 1]
end = [11, 30]

longFlower = array[0]
while True:
  count = 0
  for i in range(index, n):
    # 시작일보다 아래에 있는 꽃 탐색
    if (array[i][0] < start[0]) or (array[i][0] <= start[0] and array[i][1] <= start[1]):
      # 가장 늦게까지 피는 꽃 탐색
      longFlower = max(longFlower, array[i], key = lambda x: (x[2], x[3]))
      count += 1
      index = i + 1 # 루프 횟수를 줄이기 위한 변수
    else:
      break

  # 시작 날짜를 꽃의 끝나는 날로 재지정
  start[0], start[1] = longFlower[2], longFlower[3]
  result += 1

  # 조건을 만족한 경우 루프 탈출
  if start[0] > end[0]:
      break
  # 조건을 하나도 찾지 못한경우 경우의 수가 없음
  elif count == 0:
    result = 0
    break

print(result)

220719 solved

뭔가.. 뭔가 좀 깔끔하지 않은 것 같은데 아무튼 풀었음

처음에 주석으로 워크플로우 대충 구상해놓고 하니까 수월했음

 

[BFS/DFS]

 

2102: 배수(Hard)

from collections import deque

n = int(input())

def bfs(pivot, start):
  queue = deque([start])

  while queue:
    val = queue.popleft()

    # 최대 범위보다 크면 루프 종료
    if val >= 2**64:
      return 0
    # 나누어지면 공배수라는 뜻
    elif val % pivot == 0:
      return val

    # 큐에 값 추가. 그림으로 그리면 이진트리와 비슷한 그림이 그려짐
    queue.append(val * 10)
    queue.append(val * 10 + 1)

print(bfs(n, 1))

220716 solved

BFS 이용. 이상하게 문제 이해가 오래걸려서 풀이를 좀 찾아본 뒤에서야 이해했음

 

2605: 캔디팡

# 2605 캔디팡 220715

width, height = 7, 7

graph = []
for i in range(height):
  graph.append(list(map(int, input().split())))

# 7x7 리스트 초기화
visited = [[False] * width for _ in range(height)]

count = 0

def dfs(x, y, color):
  global count
  
  if x <= -1 or x >= width or y <= -1 or y >= height:
    return False

  # 방문하지 않음과 동시에 같은 색상인것만 골라서 방문처리
  if visited[x][y] == False and graph[x][y] == color:
    visited[x][y] = True
    count += 1
    dfs(x+1, y, color)
    dfs(x-1, y, color)
    dfs(x, y+1, color)
    dfs(x, y-1, color)
    return True

  return False

result = 0

for i in range(width):
  for j in range(height):
    dfs(i, j, graph[i][j])
    # 3개 이상의 색이 연달아 있는 경우만 카운팅
    if count >= 3:
      result += 1
    count = 0

print(result)

220715 solved

DFS 이용

 

2610: 그림판 채우기

# _: 색칠되지 않은 부분, *: 색칠된 부분

paint = []
for i in range(10):
  paint.append(list(input()))

x, y = map(int, input().split())

def dfs(array, _x, _y):
  if _x <= -1 or _x >= 10 or _y <= -1 or _y >= 10:
    return

  # 보통 인지하는 x,y와 배열의 행렬은 반대이므로 바꿔서 사용
  if array[_y][_x] == '_':
    array[_y][_x] = '*'
    dfs(array, _x+1, _y)
    dfs(array, _x-1, _y)
    dfs(array, _x, _y+1)
    dfs(array, _x, _y-1)
  else:
    return

dfs(paint, x, y)

for i in range(10):
  for j in range(10):
    print(paint[i][j], end='')
  print("")

220716 solved

일반적인 DFS. visited 처리를 따로 안해도 됨

 

3212: 위상정렬

from queue import PriorityQueue

v, n = map(int, input().split())

graph = [[0] for _ in range(v+1)]
indegree = [0] * (v+1)
p_queue = PriorityQueue()

for i in range(n):
  x, y = input().split()
  x, y = int(x), int(y)
  graph[x].append(y)
  indegree[y] += 1

for i in range(1, v+1):
  if indegree[i] == 0:
    p_queue.put(-i)

while not p_queue.empty():
  here = -p_queue.get()
  print(here)

  for i in graph[here]:
    indegree[i] -= 1
    if indegree[i] == 0:
      p_queue.put(-i)

정답은 이건데 솔직히 봐도 아직 모르겠음

 

 

 

삽질의 기록들

# v: 정점의 개수 n: 간선의 개수. 인덱스는 둘다 1부터 쓸것

from queue import PriorityQueue

v, n = map(int, input().split())

# 열n+1 행v+1. 행 인덱스 0은 버릴거기때문에 v만 한개 더 크게
# 앞쪽이 가로길이(열/간선), 뒤쪽이 세로길이(행/정점)
graph = [[0] for _ in range(v+1)]

# 탐색 시작 노드를 저장할 변수
init_v = 0

for i in range(n):
  x, y = input().split()  
  graph[int(x)].append(int(y))
  if i == 0:
    init_v = int(x)
    
result = []

def dfs(array, start, visited):
  # 우선순위 큐 사용 선언
  p_queue = PriorityQueue()
  p_queue.put(start)
  visited[start] = True

  # 큐가 빌때까지
  while not p_queue.empty():
    v = p_queue.get() 
    # 우선순위 큐를 통해 나온 값은 언제나 최소값과 중복이 아님을 보장받는다
    result.append(v)

    for i in range(1, len(array[v])):
      if not visited[array[v][i]]:
        p_queue.put(array[v][i])
        visited[array[v][i]] = True
        
  return

# 방문을 체크하는 리스트
visitedCheck = [False] * (v+1)

dfs(graph, init_v, visitedCheck)

# 주어진 노드 개수만큼 들어가지 않았다면 탐색을 실패했다는 소리
# 애초에 중복은 우선순위 큐에 들어가지 않으니 순회인지, 끊긴건지는 알 수 없음
if len(result) <= v-1:
  print(-1)
else:
  for i in range(len(result)):
    print(result[i])

반례를 보니 우선순위 큐로 풀리네? 해서 짜놨더니 막히고 다음 반례를 확인하니까 아니었음

여전히 헤메고 있는중