본문 바로가기

문제 노트/백준

 (102)
스승님 찾기( BOJ 15979 ) 문제 : https://www.acmicpc.net/problem/15979 15979번: 스승님 찾기 첫째 줄에 (M, N) 좌표로 이동하기 위해 필요한 최소 순간이동 횟수를 출력한다. www.acmicpc.net 문제 파악하기 (0, 0)에서 (M, N)까지 이동하는데 필요한 순간이동 횟수를 구하는 문제입니다. 순간이동은 항상 현재 좌표에서 볼 수 있는 좌표로 이동할 수 있습니다. 떠올릴 수 있는 가장 간단한 방법은 최대공약수를 구하는 것입니다. 입력된 좌표값 (M, N)의 최대공약수를 구하면 (0, 0)에서 해당 숫자까지 이동하는 최단 직선 거리로 이동하는 순간이동 횟수를 구할 수 있습니다. 하지만 이 방법은 아쉽게도 반례가 있습니다. 만약 (3, 3)으로 이동하려면 어떻게 해야할까요? (3, 3)..
RSA( BOJ 13618 ) 문제 : https://www.acmicpc.net/problem/13618 13618번: RSA A única linha da entrada contém três inteiros N, E, e C, onde 15 ≤ N ≤ 109 , 1 ≤ E < N e 1 ≤ C < N, de forma que N e E constituem a chave pública do algoritmo RSA descrita acima e C é uma mensagem criptografada com essa chave pública. www.acmicpc.net 문제 파악하기 포르투갈 언어로 작성되어 있는 문제라 조금 읽기 어려웠지만, 단순히 RSA 알고리즘을 기반으로 만든 문제이기 때문에 문제를 푸는 데에는 큰 무리가 없습..
추첨상 사수 대작전! (Hard) ( BOJ 20412 ) 문제 : https://www.acmicpc.net/problem/20412 20412번: 추첨상 사수 대작전! (Hard) 한 줄에 걸쳐 준표가 좋아하는 소수 m, 참가자들이 정한 Seed, 시연으로 공개된 X1, X2 이 주어진다. 항상 가능한 상황만 입력으로 주어진다. www.acmicpc.net 문제 파악하기 추첨상 사수 대작전! 시리즈의 마지막 문제입니다. 보통 시리즈로 나오는 문제들은 난이도가 올라갈수록 탐색의 범위를 점차 줄이며, 마지막에는 수식을 사용한 O(1) 알고리즘을 요구하게 됩니다. 이 문제 역시 O(1) 알고리즘을 사용해야 문제를 해결할 수 있습니다. 이 문제에서 주로 사용하는 연산자는 바로 모듈러(%) 입니다. 따라서, 우리는 모듈러(%) 연산을 적절하게 사용하여 a의 값을 구할..
천상용섬( BOJ 12758 ) 문제 : https://www.acmicpc.net/problem/12758 12758번: 천상용섬 테스트케이스마다 승균이가 벨 수 있는 모든 경우의 수를 출력한다. 출력은 개행으로 구분되어야 한다. 정답이 커질 수 있으니 \(1,000,000,007\)로 나눈 나머지를 출력한다. www.acmicpc.net 문제 파악하기 제시된 N개의 약수를 오름차순으로 나열하는 경우의 수를 구하는 문제입니다. N의 개수는 300개라서 많지 않지만 입력되는 숫자가 최대 1,000,000이기 때문에 단순히 모든 숫자를 비교하기에는 너무 오랜 시간이 필요합니다. 그렇기에 우선, 빠르게 구할 수 있는 값부터 먼저 구해봅시다. 어떤 수(K)의 약수를 구하기 위해서는 1부터 K까지의 수를 모두 비교할수도 있지만, 1부터 √K까..
주식( BOJ 11501 ) 문제 : https://www.acmicpc.net/problem/11501 11501번: 주식 입력의 첫 줄에는 테스트케이스 수를 나타내는 자연수 T가 주어진다. 각 테스트케이스 별로 첫 줄에는 날의 수를 나타내는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고, 둘째 줄에는 날 별 주가를 나타 www.acmicpc.net 문제 파악하기 주식을 어느 날에 팔아야 최고 이익이 나는지 파악하는 문제입니다. 입력 값이 최대 1,000,000개이기 때문에 왠만하면 단순 반복문으로 알고리즘을 설계해야 한다는 점에 유념한다면 어렵지 않게 문제를 풀 수 있습니다. 문제 해결하기 문제를 풀기 위해서는 언제 주식을 팔아야 하는지 알아야 합니다. 최고의 이익을 내기 위해서는 가장 주가가 비싼 날에 판매를 해야합니..
체인( BOJ 2785 ) 문제 : https://www.acmicpc.net/problem/2785 2785번: 체인 희원이는 그의 다락방에서 N개의 체인을 찾았다. 각각의 체인은 몇 개의 고리로 연결되어 있는데, 각각의 고리는 최대 두 개의 인접한 고리를 가질 수 있다. 각각의 고리는 열고 닫을 수 있다. 그 www.acmicpc.net 문제 파악하기 N개의 체인을 하나로 연결하기 위해 필요한 고리의 최소 개수를 구하는 문제입니다. 각각의 고리는 분리되어 다른 체인들을 연결할 수 있으며, 최대 2개의 체인을 연결할 수 있습니다. 문제를 분석해보면 결국 체인, 즉 숫자와 숫자 사이를 연결하기 위해 사용되는 고리의 개수를 구하는 문제입니다. 따라서, 연결에 사용되는 고리의 개수를 줄이기 위해서는 하나의 체인을 전부 다른 체인을 연..
문자열 장식( BOJ 1294 ) 문제 : https://www.acmicpc.net/problem/1294 1294번: 문자열 장식 첫째 줄에 단어의 개수 N이 주어진다. N은 최대 20이다. 둘째 줄부터 N개의 줄에 단어가 주어진다. 단어는 최대 1,000글자이고, 공백은 없이 알파벳 대문자로만 구성되어 있다. www.acmicpc.net 문제 파악하기 N개의 문자를 적절하게 분해해서 사전순으로 가장 앞에 있는 하나의 문자를 만드는 문제입니다. 모든 문자의 순서를 맞춰야 하기 때문에 앞에서부터 하나씩 가져와야합니다. 문제를 처음 보면 사전순으로 가장 빠른 문자를 마냥 선택하면 될듯 하지만 aaa / aab 와 같이 동일한 문자가 반복될 때, 어떤 문자에서 a를 가져오는지에 따라 결괏값이 달라지기에 좀 더 세밀한 조건이 필요합니다. 문..
Escaping( BOJ 20041 ) 문제 : https://www.acmicpc.net/problem/20041 20041번: Escaping 첫 번째 줄에는 경찰의 수 N이 주어진다. 단, 1 ≤ N ≤ 500,000이다. 그 다음 N 개의 줄에는 각 경찰의 초기 위치의 좌표 (xi, yi)가 공백을 사이에 두고 주어진다. 다음 줄에는 도둑의 초기 위치의 좌 www.acmicpc.net 문제 파악하기 N명의 경찰이 1명의 도둑을 잡을 수 있는지 여부를 파악하는 문제입니다. 정답이 Yes / No로 나오는 대표적인 결정 문제라고 할 수 있습니다. 경찰과 도둑은 항상 상하좌우 인접한 격자 점으로 이동하며, 번갈아 가며 한 칸씩 움직일 수 있기 때문에 경찰이 먼저 도달하거나 도둑과 함께 동시에 도달하는 위치에서는 항상 경찰이 도둑을 잡을 수 ..

티스토리툴바