Baekjoon
-
26646번 알프스 케이블카알고리즘 2023. 2. 16. 10:59
문제 설명 이번 문제는 여러 산맥의 정상을 다른 산의 정상으로 잇는 와이어를 설치해서 이동할 경우, 노선의 설치 비용을 최소화하는 경우를 구하는 문제입니다. 와이어의 설치 비용 - 와이어 길이의 제곱 노선의 설치 비용 - 와이어의 설치 비용의 합 문제 풀이 아이디어 와이어 설치 비용의 최소값 위의 사진 예시를 보도록 하겠습니다. A-B-C를 잇는 경우와 A-C를 잇는 경우의 설치 비용을 비교해보면, A-B-C를 잇는 경우의 설치 비용은 66 A-C를 잇는 경우의 설치 비용은 122가 됩니다. 위에서 확인할 수 있듯이, 산 정상을 하나라도 건너 뛰어서 와이어를 잇게 된다면 설치 비용이 커짐을 알 수 있습니다. (모든 산은 직각 이등변 삼각형이므로 어떤 예시를 들게 되더라도, 정상 하나를 건너 뛰어서 와이어..
-
11501번 주식알고리즘 2023. 2. 15. 12:05
문제 설명 홍준이가 미래의 주식 가격 변동에 대한 정보를 알고 있고, 매일 아래 3가지 행동 중 한 개의 행동만 할 경우, 벌 수 있는 최대 이익을 구하는 문제입니다. 주식 하나를 산다 원하는 만큼 가지고 있는 주식을 판다 아무것도 안한다 문제 풀이 아이디어 주식을 사는 타이밍 홍준이가 주식 가격 정보를 알고 있으므로, 주식이 오를 때까지는 계속 사고 최고점일 경우에 모두 팔아버리면 최고 이익이 나게 됩니다. 최고점 이후 최고점이 지나고 난 뒤에도 고점이 있을 수 있습니다. 그러므로 최고점 이후 날짜들에 대한 주식 최고값을 다시 구해주고, 그 날짜가 되기 전까지 주식을 모두 사면 이익을 가질 수 있게 됩니다. 풀이 최고점 찾기의 반복 우선 첫 날부터 마지막 날까지, 최고점이 되는 날을 찾고 첫 날부터 최..
-
10476번 좁은 미술관알고리즘 2023. 2. 13. 11:37
문제 설명 이번 문제는 가로로 두칸 세로로 N칸이 있는 미술관에서 각 방마다 가치가 정해져 있을 때, 아래 규칙대로 K개의 방을 닫아서 공개된 방의 가치의 합을 최대로 하는 경우를 구하는 문제입니다. 한쪽 끝의 두 방중 적어도 한 방에는 방문할 수 있어야 하고 다른 쪽 끝의 두 방중 한 방으로 나갈 수 있어야 한다. 즉, 같은 줄의 두 방을 모두 닫거나 대각선으로 붙어있는 두 방을 닫아서는 안 된다. 문제 풀이 아이디어 한 줄을 닫을 수 있는 방법의 수 한 줄에 있는 두 방을 모두 동시에 닫을 수 없으므로, 한 줄을 닫는 방법은 아래와 같습니다. 왼쪽만 닫는다 오른쪽만 닫는다 모두 열어 둔다 위와 같이 3가지 경우만 있습니다. 최대값을 구하는 방법 위에서부터 닫을 방을 정할 때, 현재 위치에서 각 방법에..
-
20207번 달력알고리즘 2023. 2. 10. 22:16
문제 설명 이번 문제는 다음과 같은 달력에 일정을 표시해둘 경우 코팅지를 사용하는데, 다음과 같은 규칙으로 코팅지를 붙일 경우 필요한 코팅지의 면적을 구하는 문제입니다. 연속된 두 일자에 각각 일정이 1개 이상 있다면 이를 일정이 연속되었다고 표현한다. 연속된 모든 일정은 하나의 직사각형에 포함되어야 한다. 연속된 일정을 모두 감싸는 가장 작은 직사각형의 크기만큼 코팅지를 오린다. 달력은 다음 규칙을 따릅니다. 일정은 시작날짜와 종료날짜를 포함한다. 시작일이 가장 앞선 일정부터 차례대로 채워진다. 시작일이 같을 경우 일정의 기간이 긴 것이 먼저 채워진다. 일정은 가능한 최상단에 배치된다. 일정 하나의 세로 길이는 1이다. 하루의 폭은 1이다. 문제 풀이 아이디어 정렬 일정을 붙이는 것에 순서가 있다보니 ..
-
17505번 링고와 수열알고리즘 2023. 2. 9. 16:39
문제 설명 이번 문제는 1~N까지의 수로 이루어진 수열 A에서 i A[j]인 개수가 K개일 수 있는지 구하는 문제입니다. K개인 수열이 있다면 해당 수열을 출력(조건을 만족하는 수열의 개수가 여러 개라면 한 개만 출력)합니다. K개인 수열이 없다면 -1을 출력합니다. 문제 풀이 아이디어 문제의 조건을 이용하는 방법 수열 A에서 i A[j]를 만족할 수 있는 경우는 앞쪽의 원소가 뒤쪽의 원소보다 큰 경우입니다. N=5인 경우에 대한 예시를 들어보도록 하겠습니다. (A = [1,2,3,4,5]) 위의 조건을 만족하는 개수가 0인 경우를 생각해보면 앞쪽의 원소가 뒤쪽의 원소보다 항상 작은 경우입니다. -> [1, 2, 3, 4, 5] 위의 조건을 만족하는 개수가 ..
-
5002번 도어맨알고리즘 2023. 2. 8. 10:15
문제 설명 이번 문제는 클럽의 출입구에서 남녀 수의 차이를 맞춰주는 도어맨이 있고 도어맨이 기억할 수 있는 수 차이의 최대값이 주어졌을 때, 이 도어맨이 아래 규칙을 지키면서 사람들을 들여보낼 수 있는 최대 수를 구하는 문제입니다. 줄의 맨 앞에 줄 서 있는 사람을 들여보내야 되는 것은 아니다. 남녀 수의 차이를 고려해 두 번째 사람을 들여보내도 된다. 문제 풀이 아이디어 탐색 이번 문제는 주어진 순서를 모두 파악해야 하므로 모두 탐색해봐야 한다. 비교는 절대값으로 앞에서부터 사람을 들여보낼 때, 도어맨이 기억할 수 있는 수 차이의 최대값을 넘기지 않는 선에서 앞 사람이나 두 번째 사람을 들여보내야 합니다. 여기서, 남자를 1, 여자를 -1이라 하면 첫 번째 사람이나 두 번째 사람을 들여보냈을 경우 현재..
-
17615번 볼 모으기알고리즘 2023. 2. 6. 10:04
문제 설명 이번 문제는 빨강색, 파랑색 볼이 주어졌을 때, 다음과 같은 규칙으로 볼을 이동시켜서 같은 색의 볼들이 모여있도록 할 때의 최소 이동횟수를 구하는 문제입니다. 바로 옆에 다른 색의 볼이 있으면 그 볼들을 모두 뛰어넘을 수 있다. 옮길 수 있는 볼의 색은 한 가지이다. 처음에 빨간 볼을 움직였다면 다음에는 파란 볼을 움직여야 한다. 문제 풀이 아이디어 공을 최소 횟수로 움직일 수 있는 순서 공들을 움직일 경우 바로 옆의 다른 색의 볼은 모두 뛰어넘을 수 있다는 규칙이 있다. 이것을 만족하되, 공을 모으는 최소 이동횟수를 구하는 움직이는 순서는 가장 자리 쪽의 공을 먼저 움직이는 것이다. 그림 1에서 파란 색 공을 움직이는 상황을 살펴보겠습니다. 만약, 4번 공을 먼저 움직인다면 6번 앞에 5번에..
-
18352번 특정 거리의 도시 찾기알고리즘 2023. 2. 5. 11:24
문제 설명 이번 문제는 각 도시마다 다른 도시로 갈 수 있는 단 방향 도로가 존재할 경우, 주어진 도시 X에서 최단 거리 K로 갈 수 있는 도시를 출력하는 문제입니다. 문제 풀이 아이디어 bfs 최단거리로 갈 수 있다는 말을 보자마자 bfs를 떠올렸습니다. 풀이 변수 단방향 도로에 대한 정보를 저장할 roads dict를 선언했습니다. bfs를 이용한 풀이를 위해 우선 queue 배열을 선언했습니다. 그리고 원소는 [0, X]와 같은 형식으로 두었습니다. (0 => 현재 이동한 횟수, X => 현재 도시 ) 그리고 해당 도시를 방문했음을 알려주는 boolean 타입의 visited 배열을 선언해주었습니다. (visited의 원소는 False로 채워줍니다.) 결과값을 저장할 result 배열도 선언해주었습..