20230201 - 20230206

20230201 부터 20230206 까지 푼 백준 문제들

1041 주사위

• 완성된 정육면체는 큐브 모양이며 맨 아래면은 보이지 않음
• 큐브를 이루는 블록들의 겉으로 보여지는 면은 1, 2, 3개 중 하나
  • 면이 1개 보이는 블록 개수 = 4 * (n - 2)(n - 1) + (n - 2)(n - 2)
  • 면이 2개 보이는 블록 개수 = 4 * (n - 2) + 4 * (n - 1)
  • 면이 3개 보이는 블록 개수 = 4개 (가장 상단 모서리 4개)

• 주사위는 마주보는 면을 제외하고 모든 면이 인접
  • 따라서 마주보는 면 중 최소를 찾아 리스트 저장
• 리스트에 저장된 세 값으로 결과 구하기

3079 입국심사

입력 값의 범위와, 최소 시간을 구한다는 문제 내용을 보고 이분 탐색을 떠올렸다. 일단 이분 탐색인 것 같은데, 어떤 값을 기준으로 탐색 범위를 나눠야 하는지 갈피를 잡기 어려웠다.
일단 mid가 우리가 구하고자 하는 최소 시간을 찾기 위한 “총 시간” 을 나타내는 것을 알고 있었지만, 그 시간동안 몇 명이 심사를 받을 수 있는지 구해야 겠다는 생각이 바로 떠오르지 않았다 ㅠㅠ.
반복문을 사용해서 입력 받은 각 심사관마다 걸리는 시간들을 각각 총 시간(mid)에 나눠주면 각 심사관마다 몇명을 심사 할 수 있는지 알 수 있다.

즉, (mid // n번째 심사 소요시간) == n번에서 심사받을 수 있는 인원수 이다. 이걸 각 심사 시간마다 구해서 전부 더하면 mid 시간동안 심사를 받을 수 있는 총 인원수가 구해진다.

for time in times:
	people += mid // time

이 총 인원수와 우리가 처음에 입력받은 인원수를 비교하여 mid 값을 수정 하면 되는 것이다. 입력받았던 인원수 보다 people 값이 크다면 end를 줄이고, people 값이 작다면 start를 키워준다.

9465 스티커

문제 보고 DP 인 것 파악함
각 위치에 올 수 있는 최대값이 무엇인가 계산

13305 주유소

값이 싼 주유소를 들려서 총 주유비를 최소로 만들어야한다.
현재 주유소 가격이 다음 주유소 가격보다 비싸다면 다음 주유소를 갈 만큼만 주유를 하고, 현재 가격이 다음 주유소 가격보다 싸다면 자기 자신보다 저렴한 주유소를 만날 때 까지의 거리만큼 주유를 해야한다.

따라서 price 배열에 주유소 가격 정보가 저장 되어 있을 때,

cost = price[0]
res = 0

for i in range(n - 1):
	cost = min(cost, price[i])
	res += dis[i] * cost

이렇게 이전 주유소 값과 현재 주유소 값을 비교해서 더 적은 값을 더해주면서 진행하면 된다.

13549 숨바꼭질 3

거리와 관련된 문제인 것 같은데.. 가중치가 한 개가 아니라서 어떤식으로 풀어야 할 지 감이 안왔다. 찾아보니 큐를 두개 사용하면 되는데 deque가 양방향 이용이 가능하니 하나는 왼쪽을 하나는 오를쪽을 사용하면 된다고 한다.
- 기본적으로 bfs 문제 풀이 방식이므로 visit 여부를 확인 해준다. 방문한 적 없는 곳으로만 이동하며 얼마나 이동해왔는지 표시를 해야한다.
- 순간이동은 가중치가 0, 이동은 1이기 때문에 순간이동이 우선적으로 탐색되어야한다.
- 따라서 큐에 삽입할 때, 순간이동인 경우에는 appendleft()를 해주어 순번을 당기고, 이동인 경우에는 일반적인 경우와 같이 append()해준다.
- 반복문을 이용해서 X + 1, X - 1, X * 2를 큐에 넣어준다. 예를들어 3이 시작 노드라면 큐에는 6, 4, 2가 순서대로 들어가며, 순간이동을 한 경우인 6이 다음으로 탐색할 노드가 된다.

18111 마인크래프트

나는 브루트포스로 풀 수 있는지 검증하는걸 어려워하는듯.. 어떻게 풀어야하는지 모르겠어서 풀이 봤고 0층부터 256층까지 전부 확인하면 되는 문제였다. 256 * 500 * 500 = 64000000이므로 1초 내에 연산 가능한 문제..!!! 위에 주사위 문제 풀 때, 딱히 떠오르는 방법이 없으면 규칙을 찾아보자고 했었는데 이 문제에서는 규칙조차 찾기가 어려웠다.. 규칙조차 찾기 어려우면 단순한 방법으로 총 연산이 1억번 이내인지 확인해보자구… ㅠ