AndroidTeacher

www.acmicpc.net/problem/1193 1193번: 분수찾기 첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다. www.acmicpc.net 문제 설명 문제에서, 나열된 분수들을 지그재그 순서로 찾아간다고 했는데, 이 재그재그를 설명하는 예시가 부족해 보였다. 그래서 초반에 이 지그재그 규칙을 찾아내느라 시간을 많이 썼던 것 같다. X가 주어지면 X번째 분수를 출력하면 된다. ( 5번째 분수는 2/2 ) 풀이 과정 위의 그림을 보면 일정한 규칙이 나타남을 알 수 있다. 라인에 있는 분수의 개수는 1라인은 1개, 2라인은 2개, 3라인은 3개, 4라인은 4개... 이런 식으로 늘어감을 알 수 있다. 짝수라인은 시작점에서 끝점으로 갈수록 분자가 1씩 늘어가고 분모가 1씩 감소하며 홀수..

www.acmicpc.net/problem/2292 2292번: 벌집 위의 그림과 같이 육각형으로 이루어진 벌집이 있다. 그림에서 보는 바와 같이 중앙의 방 1부터 시작해서 이웃하는 방에 돌아가면서 1씩 증가하는 번호를 주소로 매길 수 있다. 숫자 N이 주어졌 www.acmicpc.net 문제 설명 위 링크의 문제에 나온 것 처럼, 입력 한 숫자가 들어있는 칸에 가기 위해서 1번 칸 부터 거쳐야 하는 칸의 수를 출력하면 된다. 풀이 과정 1번이 가운데 기준으로 첫 번째 주기라고 했을 때 1, 2번째 주기는 2~7 3번째 주기는 8~19 4번째 주기는 20~37 5번째 주기는 38~61 이렇게 나타나며 각 주기의 끝자리가 6의 배수처럼 늘어나는 것을 알 수 있다. 즉, 1->7->19->37->61 은 6..

www.acmicpc.net/problem/2847 2847번: 게임을 만든 동준이 학교에서 그래픽스 수업을 들은 동준이는 수업시간에 들은 내용을 바탕으로 스마트폰 게임을 만들었다. 게임에는 총 N개의 레벨이 있고, 각 레벨을 클리어할 때 마다 점수가 주어진다. 플레이어 www.acmicpc.net 문제 설명 첫째 줄에 레벨의 수 N이 주어지고, 다음 줄부터 N+1줄까지 게임 레벨의 난이도가 주어진다. 이전 게임의 레벨은 반드시 다음 게임의 레벨보다 낮아야 하는데, 입력의 상태는 이전 게임이 다음 게임보다 레벨이 높은 경우가 존재한다. 최소한의 횟수로 레벨을 오름차순으로 나타내어야 하며, 레벨 1감소가 1회이다. 풀이 과정 현재 게임이 다음 게임보다 레벨이 낮게 하려면 어떻게 해야할까? 다음 게임의 레벨..

www.acmicpc.net/problem/1449 1449번: 수리공 항승 첫째 줄에 물이 새는 곳의 개수 N과 테이프의 길이 L이 주어진다. 둘째 줄에는 물이 새는 곳의 위치가 주어진다. N과 L은 1,000보다 작거나 같은 자연수이고, 물이 새는 곳의 위치는 1,000보다 작거나 www.acmicpc.net 문제 설명 수리공이 물이 새는 파이프를 테이프로 수리한다. 테이프는 무한 개 갖고 있으며, 최소한의 테이프를 사용하여 수리해야 한다. 물이 새는곳을 막을 때, 그 위치의 좌우로 0.5만큼씩을 더 막아줘야 물이 새지 않는다. 테이프는 자를 수 없으며, 겹칠수는 있다. 또, 물이 새는 곳의 위치는 자연수이다. 풀이 과정 최소한의 개수로 최대의 이익을 취해야 하는 그리디 알고리즘 문제이다. 먼저 테이..

www.acmicpc.net/problem/1439 1439번: 뒤집기 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모 www.acmicpc.net 문제 설명 0과 1로만 이루어진 문자열 S이 주어진다. 이 문자열S을 모두 같은 숫자로 이루어진 문자열로 바꾸려고 하는데, 연속된 하나 이상의 숫자를 뒤집을 수 있다. (0을 1로, 1을 0로) 예를 들어, 1001001이 있으면 1001001 -> 1111001 -> 1111111 과 같이 바꿀 수 있다. 주어진 문자열을 바꾸는데 필요한 최소 횟수를 출력하면 된다. 풀이 과정 문제를 보고, 가장 먼저 떠올랐던..

www.acmicpc.net/problem/4796 4796번: 캠핑 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, L, P, V를 순서대로 포함하고 있다. 모든 입력 정수는 int범위이다. 마지막 줄에는 0이 3개 주어진다. www.acmicpc.net 문제 설명 입력으로 L, P, V를 입력받는다. ( 1 < L < P < V ) 이는 총 V일간의 휴가기간동안 캠핑장을 연속하는 P일 중, L일동안 이용할 수 있다는 뜻이다. 예를 들어, V = 20, P = 8, L = 5 이면, 총 휴가기간 20일 중 캠핑장을 연속하는 8일중 5일간 이용할 수 있다는 뜻이다. 그래서 처음 5일을 이용하고 그 뒤 3일은 이용을 못하고 다시 5일을 이용하고 이런 식으로 전..

www.acmicpc.net/problem/1783 1783번: 병든 나이트 첫째 줄에 체스판의 세로 길이 N와 가로 길이 M이 주어진다. N과 M은 2,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 설명 병든 나이트는 보통 체스의 나이트와는 다르게 아래의 네가지 방법으로만 움직일 수 있다. 2칸 위로, 1칸 오른쪽 1칸 위로, 2칸 오른쪽 1칸 아래로, 2칸 오른쪽 2칸 아래로, 1칸 오른쪽 이 때, 맵의 크기가 N * M으로 주어질 때, 병든 나이프가 방문할 수 있는 칸의 최대 개수를 구하면 된다. (단, 이동 횟수가 4번 이상이라면, 4가지 방법을 한 번씩 모두 사용해야 한다.) 풀이 과정 병든나이트는 이동 시, 무조건 오른쪽으로는 이동을 하게 되어있고, 위 아..

www.acmicpc.net/problem/2217 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net 문제 설명 N개의 로프를 이용해 물체를 들어올린다. N개의 로프는 주어진 중량만큼까지만 물체를 들어올릴 수 있으며, K개의 로프를 이용하여 W무게의 물체를 들어올린다면, 모든 로프에 똑같이 W / K 만큼의 중량이 걸리게 된다. 입력으로 각 로프들에 대한 정보가 주어지면, 이 로프들을 이용하여 버틸 수 있는 최대 중량을 출력하면 된다. 풀이 과정 A라는 로프가 버틸 수 있는 중량이 최대 A라면 이 로프..

www.acmicpc.net/problem/13305 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 문제 설명 N개의 도시가 일렬로 나열되어 있고, 각 도시간의 거리를 입력받는다. 그리고 그 도시에서의 리터당 주유비를 입력받는다. 이 때, 도시의 시작점에서 끝지점까지 이동하는데 드는 최소의 비용을 구하면 된다. 풀이 과정 각 도시마다 주유소의 가격이 다르기 때문에, 최소의 비용으로 최대충전을 하는 것이 목표다. 이 때, 시작점에서는 반드시 주유가 되어있어야 하기 때문에 첫 최소비용은 시작점의 가..

www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 문제 설명 수식이 문자열로 주어질 때, 적절한 괄호를 쳐서 수식의 결과값을 최소로 만들면 된다. 단, 처음과 숫자는 숫자이며, 두 개 이상의 연산자가 나타나지 않으며(++,--) 연산자는 +, -만 사용할 수 있다. 풀이 과정 그리디 알고리즘 문제이다. 최소값을 만들기 위해선 어떻게 해야할까? 마이너스 바로 뒤에 괄호를 열고 그 안의 수식을 최대로 만든 후 다시 괄호를 닫으면 된다. 처음 풀었던 방법은 바..