AndroidTeacher

www.acmicpc.net/problem/4949 4949번: 균형잡힌 세상 하나 또는 여러줄에 걸쳐서 문자열이 주어진다. 각 문자열은 영문 알파벳, 공백, 소괄호("( )") 대괄호("[ ]")등으로 이루어져 있으며, 길이는 100글자보다 작거나 같다. 입력의 종료조건으로 맨 마 www.acmicpc.net 문제 설명 괄호들의 균형이 잘 맞춰져 있는지 확인하는 문제이다. 괄호는 소괄호"()"와 대괄호"[]"가 있으며 다음과 같은 규칙이 있다. 모든 왼쪽 소괄호("(")는 오른쪽 소괄호(")")와만 짝을 이뤄야 한다. 모든 왼쪽 대괄호("[")는 오른쪽 대괄호("]")와만 짝을 이뤄야 한다. 모든 오른쪽 괄호들은 자신과 짝을 이룰 수 있는 왼쪽 괄호가 존재한다. 모든 괄호들의 짝은 1:1 매칭만 가능하..

www.acmicpc.net/problem/9012 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net 문제 설명 "( ( ) ) " or "( )( )" 등 괄호가 정상적으로 닫혔을 경우에는 YES 를 출력하고 "( ( ) ( " or "( ( ) " 등 괄호가 정상적으로 닫히지 않았을 경우에는 NO를 출력하는 문제이다. 풀이 과정 스택의 pop을 이용하기 때문에 가장 처음에는 " ) " 가 나와야 한다. 그리고 " ) " 를 꺼내지 않았는데 " ( " 가 나오는 경우도 정상적인 ..

www.acmicpc.net/problem/10773 10773번: 제로 첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000) 이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경 www.acmicpc.net 문제 설명 기본적인 스택을 이용한 문제이다. 첫째 줄에 입력할 정수의 개수 K를 입력하고 다음 K번 동안 정수를 입력받는다. 0일 경우 가장 최근에 넣은 수를 꺼내고, 나머지 경우에는 스택에 입력을 넣어주면 된다. 풀이 과정 0을 입력할 경우 가장 최근에 쓴 수를 지우라고 했으므로 스택의 pop 기능을 사용하면 된다. 마지막에는 sum함수를 이용해 스택의 모든 수를 더하면 된다..

www.acmicpc.net/problem/10828 10828번: 스택 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 문제 설명 스택을 직접 구현해보는 문제이다. push X: 정수 X를 스택에 넣는 연산이다. pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다. size: 스택에 들어있는 정수의 개수를 출력한다. empty: 스택이 비어있으면 1, 아니면 0을 출력한다. top: 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 ..

문제 설명 땅 위에 달팽이가 있으며, 이 달팽이는 V미터까지 올라가게 되는데 낮에 A미터를 올라가고 밤에 B미터를 내려간다. 단, 정상에 도착했다면 내려가지 않는다. 이 때, 달팽이가 V미터까지 올라가는데 총 며칠이 걸리는지 구하면 된다. 풀이 과정 낮에는 무조건 올라가기만 하고 밤에는 무조건 내려가기만 한다. 그래서 낮에 올라간 높이가 그 날의 최대 높이가 될 것이고, 정상에 도착하더라도 무조건 낮에 도착을 하게된다. 그래서 사실상 달팽이가 올라가야 하는 최종 높이는 V-B미터가 된다. 그리고 하루동안 올라갈 수 있는 높이는 A-B미터로 한정되어 있기 때문에 총 걸리는 일수는 (V-B) / (A-B) 이 될 것이다. 여기서 나누어 떨어지지 않고, 5.3 이런식으로 걸리게 된다면 5일안에는 도달을 못하기..

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 과 같이 바꿀 수 있다. 주어진 문자열을 바꾸는데 필요한 최소 횟수를 출력하면 된다. 풀이 과정 문제를 보고, 가장 먼저 떠올랐던..