본문 바로가기

문제 해결/BOJ117

[백준] 외판원 순회 https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 비트마스킹과 DP를 같이 활용해야하는 문제입니다. 먼저, dp[i][j]의 정의는 다음과 같습니다. 현재 i의 조합을 방문하고 현재 j에 왔을 때, 순회를 마치기 위해 필요한 최소 비용이 됩니다. 이 문제의 핵심은 순회를 하기 때문에 어디서 시작을 해도 무방합니다. 저의 경우에는 0번 노드를 시작점으로 두었으므로 visited는 1로 시작을 하게 됩니다. dp.. 2023. 4. 6.
[백준] 게임 https://www.acmicpc.net/problem/1103 1103번: 게임 줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여 있는 숫자는 1부터 9까지의 자연수 또는 www.acmicpc.net DFS + 메모이제이션을 활용하여 해결하였습니다. DFS로 탐색해나가면서 현재 위치부터 움직일 수 있는 최대 횟수를 저장하고 있고 탐색 도중 메모이제이션되어 있는 부분을 만나면 탐색을 진행하지 않고 적혀있는 값을 활용하면 됩니다. 싸이클을 탐색하는 방법은 현재 DFS로 탐색중인 경로를 visited배열로 저장하고 있다가 다음 지점이 visited가 true이면 싸이클이 발생한 경우임을 알 수 있습.. 2023. 4. 6.
[백준] 거울 설치 https://www.acmicpc.net/problem/2151 2151번: 거울 설치 첫째 줄에 집의 크기 N (2 ≤ N ≤ 50)이 주어진다. 다음 N개의 줄에는 N개의 문자로 집에 대한 정보가 주어진다. ‘#’는 문이 설치된 곳으로 항상 두 곳이며, ‘.’은 아무 것도 없는 것으로 빛은 www.acmicpc.net BFS와 우선순위 큐를 사용하여 해결하였습니다. 현재가 거울인 경우에는 기존 진행하던 방향에서 시계방향, 반시계 방향으로 90도 꺾어서 진행할 수 있습니다. 따라서, 현재가 그냥 빈 공간인지 아니면 거울을 놓을 수 있는지에 따라 다르게 진행해주면 됩니다. 여기서 주의해야할 점은 거리가 최단이 아닌 거울의 수를 최소로 해야한다는 점입니다. 거리가 최소이면 단순 큐를 사용해서 목표 지점에.. 2023. 4. 5.
[백준] 팰린드롬 분할 https://www.acmicpc.net/problem/1509 1509번: 팰린드롬 분할 세준이는 어떤 문자열을 팰린드롬으로 분할하려고 한다. 예를 들어, ABACABA를 팰린드롬으로 분할하면, {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}등이 있다. 분할의 개수의 최솟값을 출력하 www.acmicpc.net DP를 활용하여 해결하였습니다. 현재 문자가 추가되었을 때 얻을 수 있는 최소 팰린드롬 분할의 개수를 그때 그때 구해주면 됩니다. dp[i]는 i번째 문자까지 얻을 수 있는 최소 분할 개수라고 가정했을 때 ABAC로 예를 들어보겠습니다. 최초에는 A가 추가됩니다. 문자 하나는 펠린드롬이고 dp[i] = 1입니다. B를 추가해봅니다.. 2023. 4. 4.
[백준] 구간 나누기 https://www.acmicpc.net/problem/2228 2228번: 구간 나누기 N(1 ≤ N ≤ 100)개의 수로 이루어진 1차원 배열이 있다. 이 배열에서 M(1 ≤ M ≤ ⌈(N/2)⌉)개의 구간을 선택해서, 구간에 속한 수들의 총 합이 최대가 되도록 하려 한다. 단, 다음의 조건들이 만족되 www.acmicpc.net DP를 활용하여 해결하였습니다. 이전에 같은 문제를 풀었던 적이 있는데도 한참을 헤매서 간신히 풀었습니다. DP에서 가장 중요한 두가지는 초기 조건과 점화식입니다. 먼저, 점화식은 다음과 같습니다. DP[k][i][0] -> k번째 구간에 i번째 숫자를 포함시키지 않는 경우, 이와 같은 경우에는 현재 숫자가 포함이 되지 않습니다. 그러므로 DP[k][i - 1][0], D.. 2023. 4. 3.
[백준] 성곽 https://www.acmicpc.net/problem/2234 2234번: 성곽 첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 N개의 정수로 벽에 대한 정보가 주어진다. 벽에 대한 정보는 한 정수로 주어지는데, 서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, www.acmicpc.net 비트연산과 BFS를 같이 활용하는 문제입니다. 각 칸을 기준으로 BFS를 통해 탐색하는 과정에서 현재 칸에서 다음 칸으로 이동할 때 해당 방향에 벽이 있는지 여부를 체크해줘야하는데 이를 비트연산을 통해 체크해주면 됩니다. 벽 하나를 허물어서 얻을 수 있는 최대 방의 크기는 BFS를 통해 탐색하면서 방의 번호를 메기고 각 칸을 탐색할 때 사방탐색을 하면서 방의 번호가 다른 경우를 만나면 두 방.. 2023. 4. 2.
[백준] 달이 차오른다, 가자. https://www.acmicpc.net/problem/1194 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, www.acmicpc.net 비트마스킹을 활용한 BFS입니다. 현재 가지고 있는 열쇠를 저장하고 있어야하는데 이를 비트마스킹을 활용하여 저장하고 있습니다. 예를 들어, 'a' 열쇠를 가지고 있는데 'f'열쇠가 추가된다고 하면 (1 2023. 4. 1.
[백준] 공주님의 정원 https://www.acmicpc.net/problem/2457 2457번: 공주님의 정원 첫째 줄에는 꽃들의 총 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 각 꽃이 피는 날짜와 지는 날짜가 주어진다. 하나의 날짜는 월과 일을 나타내는 두 숫자로 표현된다. 예를 들어서, www.acmicpc.net 그리디 문제입니다. 먼저, 각각의 꽃이 피고 지는 월, 일을 날짜로 변환하여 저장한 다음 꽃이 지는 날을 기준으로 정렬을 해줍니다. 그 다음 현재 꽃이 이전 꽃이 피기 전에 필 수 있으면 리스트에 추가해줍니다. 그 다음 기존에 선택된 꽃들을 체크하면서 현재 꽃이 포함할 수 있는 범위에 있는 꽃들은 필요가 없으므로 리스트에서 제거해주면 됩니다. import sys INT_MAX .. 2023. 3. 31.
[백준] 세 용액 https://www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 투 포인터를 활용하여 풀이하였습니다. 용액들을 정렬해주고 가장 수가 작은 용액을 고정해두고 투포인터로 0에 가까운 조합을 찾아주면 됩니다. 만약 현재 3용액의 합이 0보다 작으면 left를 증가, 0보다 크며 right를 감소시키면서 점점 0에 가까워지게 만들면 됩니다. import sys INT_MAX = sys.maxsize sys.stdin = open("input.tx.. 2023. 3. 30.

티스토리툴바