Algorithm/BOJ

[백준 1039] 교환 (C++)

1039번: 교환 첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다. www.acmicpc.net N이 100만보다 작다는 조건 덕분에 문제를 해결할 수 있었다. 최대 10번의 교환을 수행할 수 있기 때문에, 몇 번째 교환일 때 어떤 수가 나왔는지 확인한다면 모든 경우의 수를 확인해서 최솟값을 찾을 수 있다. -> check[1000001][11] 처음 숫자가 한자릿수라면 교환이 불가능하기 때문에 -1을 출력한다. 처음 숫자가 두자릿수일 때 일의 자리가 0이라면 교환이 불가능하기 때문에 -1을 출력한다. dp를 수행하면서 교환한 수가 0으로 시작할 때는 넘긴다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1..

[백준 1368] 물대기 (C++)

1368번: 물대기 첫 줄에는 논의 수 N(1 ≤ N ≤ 300)이 주어진다. 다음 N개의 줄에는 i번째 논에 우물을 팔 때 드는 비용 Wi(1 ≤ Wi ≤ 100,000)가 순서대로 들어온다. 다음 N개의 줄에 대해서는 각 줄에 N개의 수가 들어 www.acmicpc.net 모든 논을 최소 비용으로 연결시키는 문제이다. 따라서 최소 스패닝 트리라고 생각할 수 있다. 문제의 핵심은 이미 물이 있는 논을 통해서만 물을 댈 수 있다는 것이다. 그래서 어렵게 생각한다면 우물을 파는데 가장 비용이 적은 논을 구하고.. 그 논을 통해서 가장 비용이 적은 간선을 선택하고.. 등등 케이스가 복잡한 상황이 정말 많이 생길 것이다 다익스트라에서 주로 사용했었던 방식인데 가상 노드를 하나 설정한다. 가상 노드는 논들과 연..

[백준 1322] X와 K (C++)

1322번: X와 K 첫째 줄에 X와 K가 주어진다. X와 K는 2,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net X + Y = X | Y 위 식의 의미는 다음과 같다. 두 수를 2진수로 바꾸었을 때 x와 y가 가진 비트 '1'의 위치가 모두 서로 다르다는 뜻이다. 같은 말로 X의 비트가 0인 위치에만 1이 채워져 있는 수가 Y가 될 수 있는 수이다. 문제를 풀기 위해서는 위 아이디어를 다음과 같이 응용하면 된다. 7번째 Y 값을 찾고싶을 때 7은 2진수로 바꾸면 111 이다. X를 5로 가정하면 X는 ..000101 이라고 생각할 수 있다. 여기서 비트 1의 위치는 보지않고 0인 위치를 숫자가 들어갈 수 있는 위치라고 생각하자. 따라서 7이라는 숫자가 들어갈 수 있는 비..

[백준 20928] 걷는 건 귀찮아 (C++)

20928번: 걷는 건 귀찮아 일직선 위에 놓인 $N$개의 지점 $p_i$에는 최대 $x_i$만큼 이동시켜주는 인력거꾼들이 있다. 즉, $p_i$에 있는 인력거꾼은 $p_i$, $p_i+1$, $p_i+2$, $...$, $p_i+x_i$ 중 한 지점까지 승객을 데려다준다. 세상 www.acmicpc.net 1. 현재 인력거에서 M까지 갈 수 있는지 확인한다. M까지 갈 수 있다면 결과 값을 최솟값으로 갱신한다. 2. 현재 인력거에서 갈 수 있는 인력거들을 모두 queue에 넣는다. 이때 가장 멀리있는 인력거 위치 이후부터 찾는다. 인력거를 찾게되면 그때마다 가장 멀리있는 인력거의 위치를 갱신해준다. 알고리즘 과정 입력 4 10 1 3 5 7 4 6 5 2 파란색 동그라미는 인력거의 위치를 의미한다. 파..

[백준 1486] 등산 (C++)

1486번: 등산 첫째 줄에 산의 세로크기 N과 가로크기 M 그리고, T와 D가 주어진다. N과 M은 25보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 지도가 주어진다. T는 52보다 작거나 같은 자연수이고, D는 1,000 www.acmicpc.net 다익스트라를 사용해서 풀었다. 가로와 세로의 최대 길이가 26으로 짧다. 시작점으로 되돌아와야 한다. 1. 모든 점에 대해서 원점으로 돌아오는 최단거리를 구한다. 우선순위 큐에 들어갈 수 없는 정점은 아래와 같다. 1. 현재 위치의 높이와 다음 위치의 높이 차이가 T보다 크다 2. 다음 정점에 대해서 이미 최단거리가 구해져 있다. 3. 다음 정점으로 가는 거리가 D보다 크다. 4. 다음 정점이 Map을 벗어난다. 위 4가지의 경우에 대해서 con..

[백준 1726] 로봇 (c++)

1726번: 로봇 많은 공장에서 로봇이 이용되고 있다. 우리 월드 공장의 로봇은 바라보는 방향으로 궤도를 따라 움직이며, 움직이는 방향은 동, 서, 남, 북 가운데 하나이다. 로봇의 이동을 제어하는 명령어는 www.acmicpc.net 오랜만에 푼 알고리즘 문제 명령 1. Go k: k는 1, 2 또는 3일 수 있다. 현재 향하고 있는 방향으로 k칸 만큼 움직인다. 명령 2. Turn dir: dir은 left 또는 right 이며, 각각 왼쪽 또는 오른쪽으로 90° 회전한다. 두 가지 조건을 만족하며 출발 로봇이 도착지점의 상태와 같아질 때까지 이동시키는 프로그램을 구현하면된다. 나는 K칸 만큼 움직일 때 갈 수 없는 모든 조건에 break를 걸어주어서 많이 틀렸다. 벽에 막혀서 갈 수 없는 경우에만 ..

[백준 1826] 연료 채우기 (C++)

1826번: 연료 채우기 첫째 줄에 주유소의 개수 N(1 ≤ N ≤ 10,000)가 주어지고 두 번째 줄부터 N+1번째 줄 까지 주유소의 정보가 주어진다. 주유소의 정보는 두개의 정수 a,b로 이루어 져 있는데 a(1 ≤ a ≤ 1,000,000)는 성경 www.acmicpc.net 처음에 DP 문제인줄 알고 DP로 접근을 시도했었다. dp[현재 이동한 거리][현재 가지고 있는 연료 양] 을 두면 top down DP를 통해서 쉽게 구할 수 있을거라고 생각했었다. 근데 L이 최대 100만이고 연료 양도 최대 100*10000 라서 DP 배열 자체를 할당할 수가 없었다. N과 L이 너무 커서 이건 무조건 그리디라고 생각했고 실제로 그리디로 풀수가 있었다. 1. 현재 연료를 모두 소진할 때까지 쭉 달린다. ..

[백준 1854] K번째 최단경로 찾기 (C++)

1854번: K번째 최단경로 찾기 첫째 줄에 n, m, k가 주어진다. (1 ≤ n ≤ 1000, 0 ≤ m ≤ 2000000, 1 ≤ k ≤ 100) n과 m은 각각 김 조교가 여행을 고려하고 있는 도시들의 개수와, 도시 간에 존재하는 도로의 수이다. 이어지는 m개의 줄에 www.acmicpc.net 다익스트라 알고리즘을 큰 변형없이 그냥 사용하면 되는 문제이다. 다익스트라 알고리즘에서는 현재까지 구한 시간보다 다음 정점까지 가는데 걸리는 시간이 더 긴 경우에만 다음 정점을 탐색하고, 걸리는 시간을 갱신한다. 따라서 이 조건을 빼는 경우에는 N 정점에 도달하는 경우는 무수히 많아지게 될 것이다. 다익스트라에서는 다음 정점으로 가는 시간이 가장 적은 간선부터 탐색하기 때문에 이를 응용하면, 특정 정점에 ..

[백준 14595] 동방 프로젝트(Large) (C++)

14595번: 동방 프로젝트 (Large) 첫 번째 행동으로 1번과 2번 방이 합쳐져 (1, 2), (3), (4), (5) 상태가 된다. 이후 두 번째 행동으로 2, 3, 4번 방이 합쳐져 (1, 2, 3, 4), (5)의 상태가 된다. 따라서 남아있는 동방의 수는 2가 된다. www.acmicpc.net x ~ y 사이의 모든 방은 통합해서 하나의 방으로 만든다. 통합하는 순서는 결과에 영향을 주지 않기 때문에 x가 작은 순으로 오름차순 정렬한다. 현재 통합한 y 좌표의 최댓값보다 새로 통합할 방의 x좌표가 더 크다면, ((새로운 x) - (이전 y)) 값 만큼 방의 개수가 늘어난다는 뜻이다. 만약 새로운 x의 좌표가 현재 y보다 작다면 새로운 방은 더 생기지 않는다. N에서 y의 최댓값을 뺀 값을 ..

[백준 1941] 소문난 칠공주 (C++)

1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5*5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작 www.acmicpc.net 처음에 단순 dfs로 갔다가 ㅓㅏㅗㅜ 모양으로 탐색이 불가능해서 바로 접었다. bfs로 다시 도전하는데 정점간의 상태정보를 공유할 수가 없어서 방법을 생각하다가 모든 경우의 수가 최대 25C7 = 48만으로 충분히 탐색 가능함을 깨닫고 dfs를 사용해서 상태 정보를 기록하고 구한 상태들이 서로 이어져 있는 경우를 찾는 방식으로 시도를 했다. 2차원 배열을 1차원 배열로 바꿔서 편하게 백트래킹을 할 수도 있었지만 굳이 내가 2차원 배열을 유지하면서 백트래킹을 해보려는..