본문 바로가기

알고리즘51

BOJ 18869 - 멀티버스 II 18869번: 멀티버스 Ⅱ (acmicpc.net) 18869번: 멀티버스 Ⅱ M개의 우주가 있고, 각 우주에는 1부터 N까지 번호가 매겨진 행성이 N개 있다. 행성의 크기를 알고 있을때, 균등한 우주의 쌍이 몇 개인지 구해보려고 한다. 구성이 같은데 순서만 다른 우주의 쌍 www.acmicpc.net 1차 시도 처음에 각 우주에서 행성 2개씩 비교한 후, 각 위치에 대응하는 비교한 값을 다 더해서 그 갯수로 균등한 우주의 쌍을 구했다. 이 방법은 행성이 4개 이상일 때는 작동하지 않아서 바로 포기했다. 접근방법 정렬 각 행성의 인덱스를 저장한 후, 행성의 크기로 Sort를 하게 되면 각 우주에서 행성들의 인덱스 순서는 똑같아진다. 만약 이 행성의 인덱스가 다르면 균등한 우주가 아니다. 여기에 예외가 있.. 2024. 4. 15.
BOJ 2295 - 세 수의 합 2295번: 세 수의 합 (acmicpc.net) 2295번: 세 수의 합 우리가 x번째 수, y번째 수, z번째 수를 더해서 k번째 수를 만들었다라고 하자. 위의 예제에서 2+3+5=10의 경우는 x, y, z, k가 차례로 1, 2, 3, 4가 되며, 최적해의 경우는 2, 3, 4, 5가 된다. k번째 수가 최 www.acmicpc.net 접근 방법 백트래킹, 브루트포스말고는 어떻게 풀어야할지 감이 안잡혔다. 그래서 결국 알고리즘 분류를 봤다... 이 문제에서 어떻게하면 이분탐색으로 풀수있을까 많이 생각해보았다. 무엇을 기준으로 대소비교를 할 것인가? 처음엔 원소의 인덱스를 기준으로 생각해보려고 했지만, 해당 원소의 더한 값을 구하려면 이전 원소들을 모두 3개씩 더해야 한다. 그리고 무엇을 기준으로 .. 2024. 4. 13.
BOJ 16401 - 과자 나눠주기 16401번: 과자 나눠주기 (acmicpc.net) 16401번: 과자 나눠주기 첫째 줄에 조카의 수 M (1 ≤ M ≤ 1,000,000), 과자의 수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 과자 N개의 길이 L1, L2, ..., LN이 공백으로 구분되어 주어진다. 과자의 길이는 (1 ≤ L1, L2, ..., LN ≤ 1, www.acmicpc.net 접근 방법 가장 길게 과자를 N명에게 나눠주는 문제이다. 이때 핵심이 과자를 부러뜨리면 다시 합칠 수 없다는 것이다. 예제 1을 보자. 1 2 3 4 5 6 7 8 9 10에서 3명에게 가장 긴 과자를 주려면 8 , 9 , 10을 선택하여 9와 10을 각각 1, 2 만큼 부러뜨려 8로 맞춰 주면된다. 예제 2번의 경우 한 번더.. 2024. 4. 13.
BOJ 2252 - 줄 세우기 2252번: 줄 세우기 (acmicpc.net) 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 접근방법 이번 문제는 위상정렬 문제라는 것을 사전에 알고 풀었다. 왜 위상정렬로 풀어야할지 생각해봤다. 총 N명의 학생들 중 임의의 두 학생 A와 B의 키만 비교하였다. 그리고 이렇게 잰 키를 통해 줄을 세운다. 이는 A와 B를 정점으로 생각할 때, A와 B는 단방향 간선을 가진 그래프가 된다. 이를 통해, 위상정렬하여 각 정점들의 순서를 정할 수 있기 때문에 위상정렬을 .. 2024. 4. 6.
BOJ 144999 - 주사위 굴리기 14499번: 주사위 굴리기 (acmicpc.net) 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x, y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지 www.acmicpc.net 접근 방법 정육면체인 주사위를 굴리는 과정을 어떻게 구현할지가 관건인 문제. 주사위를 X,Y로 굴리면서 밑 면의 숫자가 바뀌도록 하여야 한다. 문제에 나온 주사위 면의 인덱스가 햇갈려서 멋대로 정하여 해결했다. 2 4 1 3 5 6 0 1 2 3 4 5 처음에는 각 면에서 4방향으로 움직일 경우 어떻게 되는지 생각해보았다. 예를 들어, 0인 면이.. 2024. 4. 1.
BOJ 13335 - 트럭 13335번: 트럭 (acmicpc.net) 13335번: 트럭 입력 데이터는 표준입력을 사용한다. 입력은 두 줄로 이루어진다. 입력의 첫 번째 줄에는 세 개의 정수 n (1 ≤ n ≤ 1,000) , w (1 ≤ w ≤ 100) and L (10 ≤ L ≤ 1,000)이 주어지는데, n은 다리를 건너는 트 www.acmicpc.net 접근 방법 순서 변경이 없고, 선입선출이라는 것이기 때문에 큐를 이용하면 좋겠다고 생각했다. 1. 만약 다리 하중을 버틸 수 있으면, 큐에 트럭을 넣는다. 이때, 현재 다리 위에 올라간 트럭의 총 무게(현재 무게)에 해당 트럭의 무게를 더한다. 2. 그렇지 않으면, 큐에 공백을 넣는다. 3. q.front()가 트럭일 땐, 트럭이 다리를 다 건넌겄이므로 현재 무게에서 트럭.. 2024. 3. 31.

티스토리툴바