문제 이해 단계 https://www.acmicpc.net/problem/14888 N개의 수와 N-1개의 연산자가 주어진다. 연산자가 주어지는 방법은 공백을 구분으로 개수로 들어온다. 처음부터 덧셈, 뺄셈, 곱셈, 나눗셈이다. 나눗셈은 몫만 남고 나머지는 버린다. N개의 수 사이에 입력받은 연산자들을 마음대로 배열할 수 있을 때, 나올 수 있는 최댓값과 최솟값을 구하는 문제 문제 접근 단계 해당 문제에서 봐야 할 점은 수의 개수인 N이 최대 11개라는 것이다. 이에 따라 연산자도 최대 10개밖에 되지 않는다. 모든 연산을 하나하나 확인하면 O(n)이 n! 가 될 것인데, 11! 이기 때문에 충분히 가능하다. 하지만 사이사이에 연산자들을 차례차례 나열해 보고 계산 값의 최댓값의 최솟값을 구하는 백트래킹 ..

문제 이해 단계 문제 자체는 굉장히 심플하다. 0 ~ 9까지 숫자를 딱 한 번씩만 사용해서 K자릿수를 만드는데 아래의 두 조건을 동시에 만족하는 수가 몇 개인지 구하는 문제 1. 서로 다른 소수의 합으로 나타낼 수 있어야 함 2. M으로 나누어 떨어지지 않을 때까지 나눈다. (계속 나눈다.) 더 이상 나눌 수 없을 때의 수는 소수의 곱이다. ( 이때의 두 소수는 같아도 됨) 문제 접근 단계 일단 문제 조건에서 공통적으로 소수라는 키워드가 계속 나온다. 소수의 합이던 소수의 곱이던 알기 위해선 일단 소수를 알아야 한다. 이럴 때 쓰이는 대표적인 수학적 알고리즘은 에라토스테네스의 체이다. 이를 이용하여 K = 5 일 때 즉 5자리일 때 (99999)까지 일 때의 소수를 모두 구할 수 있다. 소수의 리스트들을..

문제 이해 단계 https://www.acmicpc.net/problem/16927 배열 돌리기 시리즈 문제 NxM 직사각형을 R번 회전시킨다. 회전시킬 때 한 칸씩 반시계 방향으로 돌아가는데, 직사각형 안에 직사각형이 있는 구조다. 그림을 보면 이해가 빠를 것이다. 이런 상황일 때 R번 회전시켰을 때의 결과를 구하는 것 문제 접근 단계 이전에 풀었던 배열 돌리기와 방향만 다르지 완전히 똑같은 문제 아닌가? 라고 생각했는데 제한 조건을 보니 아니었다. R이 최대 10^9이라는 점.. 이전 문제는 한 칸씩 이동시키는 것으로 구현했었다. 이 문제는 그렇게 하면 최악의 경우 10^9 번 이동시켜야 한다. 그럼 당연히 시간초과가 뜨겠지.. 해당 문제에서 구현해야 할 것은 어떻게든 R을 줄여서 이동하는 로직을 구..

문제 이해 단계 문제 이해하는데 좀 오래 걸렸다. 입력으로 테스트케이스 T와 알파벳(문자열)이 주어지면, 그 알파벳들을 사전순으로 배열한다고 가정한다. 사전순으로 쭉 나열했을 때, 입력으로 들어온 문자열 다음으로, 나올 문자열을 출력하는 것이 해당 문제 문제 접근 단계 해당 문제에서는 동일한 문자열에 있는 알파벳들 간의 사전순, 즉 아스키코드의 크기가 중요하다.예제 입력으로 나와있는 것으로 한번 보자. 알기 쉽게 문자 말고 사전순서의 순위로 표시해 보자. HELLO → HELOL == 21334 → 21343 DRINK → DRKIN == 15243 → 15324 SHUTTLE → SLEHTTU == 5264431 →5312446 ZOO → ZOO == 211 → 211 노란색 바탕인 숫자들은 변화가 일..

문제 이해 단계 https://www.acmicpc.net/problem/16935 문제 자체는 배열을 뒤집고 돌리고, 4분할해서 분할끼리 또 돌리고 하는 거라 이해하는 건 간단하다. 로직이 같고 방향이 다른 것으로만 쳐도 구현해야 하는 것만 3개이다. 일단 입력의 제한사항으로는 배열의 크기 NxM이 입력으로 들어오고 각각 N과 M은 100 이하의 짝수이다. 그리고 4 분할할 때의 중심은 N/2, M/2이다. 또 다른 입력으로 주어지는 R은 명령어의 횟수를 뜻한다. 이게 1000개까지 가능하다는 것은 똑같은 입력이 여러 번 들어올 수도 있는 경우도 생각해야 한다는 것이다. 문제 접근 단계 해당 문제가 일반적인 배열 돌리기랑 다른 점은, 정사각형이 아닌 직사각형이라는 것이다. 이건 90도씩 돌릴 때마다 가..

문제 이해 단계 입력으로 행(R)과 열(S)가 정수로 들어오고, 그다음에는 맵의 정보가 문자형으로 들어온다. '. ' 은 공기, 'X'은 유성, '#'은 땅을 의미한다. 여기서 구하라고 하는 것은 X는 X끼리 모두 연결되어 있고 모양이 변하지 않는다고 가정하고, 위에서 아래로 수직으로 떨어진다. 이때, 최초로 유성이 땅에 닿는 시점의 모습을 나타내라는 것이다. 입력이 주어지는 가정은 다음 조건을 따른다. 1. 적어도 한 줄 이상의 공기('. ')가 주어진다. 2. 유성은 무조건 땅 위에서만 존재한다. 3. 유성은 공기 윗줄, 땅은 공기 아랫줄에만 위치한다. 4. R과 S의 범위는 3 ~ 3000 사이 해당 조건을 만족하면서 위를 구현하라는 문제. 문제 접근 단계 언뜻 보기에는 그래프 탐색 문제처럼 보이는..

문제 이해 단계 https://www.acmicpc.net/problem/17128 입력으로 소의 수 N과 횟수 Q가 주어진다. 그 아랫줄은 소에 붙어있는 스티커의 정보가 n개 들어온다. 그리고 마지막줄에는 스티커를 바꿀 소의 번호를 순서대로 입력한다. 소는 원형을 둥글게 서있고, 소를 선택하면 해당 소의 붙어있는 번호의 -1을 곱한다. 여기서 하는 연산은 모든 가능한 경우의 수에 대해 연속하는 4개의 소의 번호에 적혀있는 수를 곱한다. 그리고 곱한 수들을 모두 더한다. 출력하는 것은 번호를 바꿀 때마다 달라지는 연산의 결과이다. 문제 접근 단계 일단 이 문제에서 핵심이 되는 부분은 4개의 연속된 수라는 점과 소들이 원형 배치되어 있다는 것이다. 위에서 만든 연산식을 계산하는 코드를 만드는 것은 그렇게 ..

문제 이해 단계 짝수 팰린드롬이라고 "수열의 길이가 짝수이고 뒤집은 후의 수열과 뒤집기 전의 수열이 동일" 하다고 정의한다. 여기서 동일하다는 것은 순서까지 동일하다는 것이다. 위에 예제를 보면 좀 더 이해하기가 편할 것이다. 입력으로 수열의 길이 N이 주어지고, 짝수개의 원소가 나열될 때, 모든 수열을 나눴을 때 짝수 팰린드롬을 만족하는지 확인한다. 만족한다면 최대 몇 개로 나눌 수 있는지 확인하는 문제 문제 접근 단계 이 문제를 풀기 위해서는 짝수 팰린드롬의 특징부터 알아내야 할 것 같다. 예제 1번에서 나온 답을 보면 (1, 1), (5, 6, 7, 7, 6, 5), (5, 5)인데, 여기서 알 수 있는 특징은 짝수 팰린드롬이 성립하려면, 각 집합을 동일한 길이로 2 등분하였을 때 대칭돼야 한다는 ..