문제https://www.acmicpc.net/problem/2597문제 설명 서로 다른 눈금 6개(빨간 점, 파란 점, 노란 점)가 있는 1cm 간격의 줄자가 존재한다.빨간 점, 파란 점, 노란 점 순서로 두 점이 겹치게 줄자를 접는다.이 때 이미 두 점이 접혀있으면, 다음 점으로 넘어간다.모든 점을 겹치게 접었을때 줄자의 길이를 구한다. 풀이두 점이 접힐 때 상황을 보자. 길이가 10인 줄자가 존재한다.빨간 점 : 2,7노란 점 : 3, 10파란 점 : 4, 5 빨간 점을 겹치도록 접으면 (2 + 7) // 2 = 4.5 위치에서 접힌다.줄자는 4.5, 전체 - 4.5의 길이로 분리가 되고 접혔을 때 전체 길이는 두 길이 중 큰 길이가 될 것이다. 위 과정을 3번 반복하게 되면 최종 줄자의 길..

문제https://www.acmicpc.net/problem/1253문제 설명N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 좋다(GOOD)고 한다.N개의 수 중에서 좋은 수의 개수를 출력하라.수의 위치가 다르면 값이 같아도 다른 수이다. 풀이문제는 단순했다. N개의 숫자중 2개의 숫자를 합했을 때 N개의 숫자에 포함되는 수를 구하면 된다.문제는 N의 크기다. N은 최대 2000개가 입력된다.따라서 완전탐색을 통한다면, $N^3 = 10^9$ 정도의 시간이 걸리기 때문에 시간초과가 발생한다.즉 이를 줄일 수 있는 방법을 고안해야 한다. 나는 결과(두 숫자의 합)와 첫 번째 숫자를 택하고 이분탐색을 통해 두 번째 숫자를 탐색했다.이러한 방식이라면 시간복잡도는 $N^2*log..

문제https://www.acmicpc.net/problem/1235문제 설명 학생들에게 고유한 학생 번호를 부여한다.학생 번호는 0에서 9 사이의 숫자로 이루어진 문자열이다.학생들의 고유 번호는 서로 다르지만 그 길이는 모두 같다.학생들의 고유 번호가 주어졌을 때, 뒤에서 k자리만 추려서 남겨 놓았을 때 모든 학생들의 학생 번호를 서로 다르게 만들 수 있는 최소의 k를 구한다. 풀이학생 번호들을 뒤에서부터 i개씩 파싱해서 서로 비교한다. set에 모든 학생번호를 넣고 set의 크기가 학생의 수와 동일할 때 i를 출력했다. 문자열의 길이만큼 역으로 반복한다.res에 현재 길이까지 슬라이싱 한 문자열을 넣는다.길이가 N과 동일하다면 현재 길이를 출력한다.코드import sysinput = sys.std..

문제https://www.acmicpc.net/problem/17141문제 설명N*N 크기의 연구소가 존재한다.연구소에는 총 N*N개의 블록이 존재하며, 그 중 M개의 바이러스를 놓으려고 한다.0은 빈 칸, 1은 벽, 2는 바이러스를 놓을 수있는 칸이다.바이러스는 상하좌우로 인접한 모든 빈 칸으로 동시에 복제되며, 1초가 걸린다.모든 빈 칸에 바이러스를 퍼트리는 최소 시간을 구한다. 풀이BFS + 조합을 사용한 탐색 문제였다. 빈칸에 M개의 바이러스를 넣어야 한다. 바이러스를 놓을 수 있는 빈칸의 개수가 M개보다 많을 수 있기 때문에, 조합을 통해 바이러스를 놓는 경우를 구한다. 바이러스는 총 10개, 칸은 최대 50*50이기 때문에 시간복잡도는 여유로웠다. 조합을 통해 바이러스 칸을 구했다면,..

문제https://www.acmicpc.net/problem/28069문제 설명 문 앞에 무한히 많은 계단이 있다. 가장 아래 계단의 번호는 0번이며, 위로 올라가면서 순서대로 번호가 붙는다. 그 중 N번째 계단에 도달해야 한다. 민희는 매번 2가지 행동 중 하나를 선택해서 총 K번 행동할 수 있다. 정확히 K번째 행동에서 N번째 계단에 도달해야 한다. 계단을 한 칸 올라간다. 지팡이를 두드려 $i + \lfloor i/2 \rfloor$ 번째 계단으로 순간이동한다. 민희는 0번째 계단에 있을 때, N번째 계단에 도달할 수 있는지 구한다. 풀이민희는 0번째 계단부터 순차적으로 계단을 오른다. 따라서 이전 값을 재사용하는 DP..

문제https://www.acmicpc.net/problem/17124문제 설명 정수 배열 A와 B가 존재한다.A는 총 N개의 서로 다른 양의 정수를 포함한다.B는 총 M개의 서로 다른 양의 정수를 포함한다.배열 A와 B를 이용해서 배열 C을 만든다.C[i]는 배열 B에 있는 값중 A[i]에 가장 가까운 값으로 정의된다.만약 해당 조건을 만족하는 값이 여러개 있는 경우, 그 중 가장 크기가 작은 값으로 정의된다.배열 C를 만들었을 때, 포함된 값들의 합을 구한다. 풀이문제를 이해해보자.A = [20,5,14,9], B = [16,8,12] 배열이 존재한다.C[i]는 A[i]에 가장 가까운 B의 값이다. 20과 가장 가까운 값은 16이므로 C[1] = 16이 될 것이다. 나와 가장 가까운 값을 찾기 위해..

문제https://www.acmicpc.net/problem/13901문제 설명특정 조건에 맞게 움직이는 로봇이 존재한다.로봇은 사용자가 지정한 방향을 일직선으로 움직인다.이동 중 벽이나 방문한 지역, 장애물을 만날 경우, 사용자가 지정한 다음 방향으로 움직인다.사용자가 지정한 다음 방향이 없다면 맨 처음 방향으로 돌아가 과정을 반복한다.움직일 수 없을 경우 동작을 멈춘다.이동이 끝났을 때 위치를 출력한다. 풀이BFS를 통해 탐색하여 풀었다. 사실 단순 구현으로 풀어도 문제 없지만, 익숙한 알고리즘으로 풀이했다.방향을 직접 해시를 통해 지정한다는 점이 문제의 특이점이라고 생각했다.해시를 통해 각 방향의 순서를 인덱스로 저장한다.BFS를 진행하면서 도착점을 탐색한다.이 때 방향이 최대 4방향이기 때문에 4..

문제https://www.acmicpc.net/problem/2904문제 설명숫자가 적혀있는 N장의 종이가 존재한다.두 개의 숫자 A와 B를 고르고, A를 나눌 수 있는 소수 X를 고른다. 그 다음 A를 지우고 A/X를 쓰고, B를 지우고 B*X를 쓴다.위 행동을 무한으로 반복이 가능할 때, 만든 수를 보고 점수를 계산한다. 점수는 종이에 적혀있는 모든 수의 최대공약수다.얻을 수 있는 최대 점수와 그에 필요한 연산 횟수를 구한다. 풀이문제를 읽어보니 소수, 최대공약수.. 이런 수학적인 용어들이 많이 나오길래 문제를 수학적으로 접근했다.먼저 간단한 예시를 통해 문제에서 요구하는 행동을 분석해보자. 예제 입력 2번으로 [8, 24, 9]배열이 주어진다.$A = 8$, $B = 24$ 를 선택했다.$A$를 나..

문제https://www.acmicpc.net/problem/20007문제 설명성현이는 이웃집에 떡을 돌린다.떡은 한번에 하나씩만 들고 갈 수 있다.집들 사이에는 총 M개의 양방향 도로가 존재한다.성현이는 하루에 X보다 먼 거리를 걷지 않고 거리가 가까운 집부터 방문한다.잠은 꼭 본인 집에서 자야 하므로 왕복 불가한 거리는 다음날에 간다.모든 집에 떡을 돌리기 위해 최소 며칠이 소요되는지 구한다. 풀이최단 거리 탐색 알고리즘을 통해 풀어야 하는 문제이다. 이 때 각 도로마다 거리가 다르다. 즉 가중치가 모두 다른 최단 거리 탐색이기 때문에, 다익스트라 알고리즘을 통해 최단거리를 탐색했다. 하지만 이 문제는 최단거리를 탐색하는 것이 문제가 아니다. X를 넘지 않으면서, 최소 몇 일 안에 모든 집을 방문할 ..

문제https://www.acmicpc.net/problem/2662문제 설명여러 기업에게 돈을 투자해서 최대의 이익을 얻고자 한다.투자는 만원 단위로 가능하다.각 기업에게 많은 돈을 투자할수록 많은 이익을 돌려준다.투자액이 정해져 있고, 기업의 개수와 금액 별 이익이 주어진다.가장 많은 이익을 얻을 수 있는 투자 방식과 이익금을 구한다. 풀이문제를 보자마자 다이나믹 프로그래밍이 생각났지만, 어떻게 구현을 해야할 지 잘 떠오르지 않았다.문제를 다시 읽어보니, 각 기업과, 기업 별 코스트로 나뉘어지는 것을 알고 보니, 배낭 문제와 유사하다고 생각했다. 기존 배낭 문제는 아이템과 코스트로 다이나믹 프로그래밍을 진행하는데, 이 문제는 하나의 아이템(기업)에 4가지의 코스트가 존재했다.따라서 기존 배낭 알고리..