문제 2018번: 수들의 합 5 어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한 www.acmicpc.net 풀이 투 포인터 알고리즘을 활용하여 해결할 수 있다. 두 개의 포인터 start와 end를 선언하고 초기값을 1과 2로 설정한다. 그리고 start가 end보다 작을 때까지 while문을 실행하며, start부터 end까지의 숫자를 더한 값을 계산한다. 만약 합이 입력받은 값과 같다면 개수를 세어준다. 합이 입력받은 값보다 크다면 start를 움직여 합을 줄이고, 합이 작다면 end를 움직여 합이 크게 해준다. 반복문은 입력받은 숫자의..

문제 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 풀이 고슴도치가 비버의 굴로 이동하는 가장 빠른 시간을 찾는 문제로 BFS로 해결할 수 있다. 탐색에서 물이 차는 것도 고려해야하기 때문에 Queue를 물과 고슴도치 두 개를 이용하여 해결한다. 물이 찰 예정인 칸으로 고슴도치는 이동할 수 없기때문에 한 싸이클을 물의 이동 -> 고슴도치의 이동의 순서로 구성하고 탐색을 수행한다. 물이나 고슴도치의 이동은 해당하는 현재 큐의 크기만큼 수행하고 빈공간을 만났을 때 이동한다. 고슴도치는 도착한 시간을 저장해주고 도착 지점에 ..

문제 3273번: 두 수의 합 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 www.acmicpc.net 풀이 입력받은 수열을 오름차순으로 정렬한 후, 두 포인터를 사용하여 원하는 합을 만드는 투 포인터 문제이다. 앞과 뒤에서 시작하는 두 개의 포인터를 조작하여 합을 조절하며 원하는 값에 도달하는데, 합이 목표값보다 크면 뒤의 포인터를 앞으로, 작으면 앞의 포인터를 뒤로 움직입니다. 두 포인터가 만날 때 반복문을 종료해준다. 투 포인터 알고리즘은 한 번의 루프마다 두 포인터 중 하나만 1씩 증가하며, 각 ..

문제 1850번: 최대공약수 모든 자리가 1로만 이루어져있는 두 자연수 A와 B가 주어진다. 이때, A와 B의 최대 공약수를 구하는 프로그램을 작성하시오. 예를 들어, A가 111이고, B가 1111인 경우에 A와 B의 최대공약수는 1이고, A www.acmicpc.net 풀이 입력받은 두 자연수의 최대 공약수가 모든 자리가 1로만 이루어져있는 두 자연수의 최대 공약수의 자리수가 된다. 따라서 입력받은 수의 최대 공약수를 구하고 최대 공약수만큼 1을 출력해주면 된다. 예제 입력 2를 보면 3 과 6의 최대 공약수는 3이고 답은 111이다. 11111 = 111 x 1001로 나타낼수 있기 때문에 답은 맞다. 풀이가 왜 성립하는지의 증명은 https://www.acmicpc.net/board/view/32..

문제 1652번: 누울 자리를 찾아라 첫째 줄에 방의 크기 N이 주어진다. N은 1이상 100이하의 정수이다. 그 다음 N줄에 걸쳐 N개의 문자가 들어오는데 '.'은 아무것도 없는 곳을 의미하고, 'X'는 짐이 있는 곳을 의미한다. www.acmicpc.net 풀이 문제에서 '누울 수 있는 자리에 몸을 쭉 뻗는다'는 조건이 있어서 헷갈릴 수 있다. 이 조건은 두 칸 이상의 빈 칸을 영식이가 누울 수 있는 하나의 공간이라는 의미이다. 예를 들어, 방의 상태가 "...X.." 인 경우 'X' 앞의 공간과 'X' 뒤의 공간으로 총 2개의 공간이 영식이가 누울 수 있는 공간이다. 이를 해결하기 위해 반복문을 통해 빈 칸을 확인하고 2칸이 될 때마다 갯수를 세어 준다. 'X'를 만날 때부터 빈칸을 다시 세어주는 ..