문제 설명임한수와 임문빈은 서로 사랑하는 사이이다.임한수는 세상에서 팰린드롬인 문자열을 너무 좋아하기 때문에, 둘의 백일을 기념해서 임문빈은 팰린드롬을 선물해주려고 한다.임문빈은 임한수의 영어 이름으로 팰린드롬을 만들려고 하는데, 임한수의 영어 이름의 알파벳 순서를 적절히 바꿔서 팰린드롬을 만들려고 한다.임문빈을 도와 임한수의 영어 이름을 팰린드롬으로 바꾸는 프로그램을 작성하시오.https://www.acmicpc.net/problem/1213 제한 사항 풀이문제를 요약하면 주어진 문자열을 재배열해 만들 수 있는 팰린드롬 중 사전순으로 가장 빠른 문자열을 출력하면 된다. 우선 팰린드롬을 만들 수 있는 조건이 있다.홀수인 문자의 개수가 1개 이하일 때만 팰린드롬을 만들 수 있다. 홀수인 ..
문제 설명우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 1원짜리 30개 또는 10원짜리 2개와 5원짜리 2개 등의 방법이 가능하다.동전의 종류가 주어질 때에 주어진 금액을 만드는 모든 방법을 세는 프로그램을 작성하시오.https://www.acmicpc.net/problem/9084 제한 사항 풀이문제를 요약하면 동전 N개가 주어졌을 때 목표를 만들 수 있는 경우의 수를 모두 구하는 것이다. 해당 문제는 유명한 dp문제이다.dp에는 i를 만들 수 있는 경우의 수를 기록할 것이다. 그럼 dp에 i를 만드는 수를 기록하는 ..
문제 설명1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 6번만 키를 비교하였고, 그 결과가 다음과 같다고 하자.1번 학생의 키 3번 학생의 키 5번 학생의 키 4번 학생의 키 4번 학생의 키 5번 학생의 키 이 비교 결과로부터 모든 학생 중에서 키가 가장 작은 학생부터 자신이 몇 번째인지 알 수 있는 학생들도 있고 그렇지 못한 학생들도 있다는 사실을 아래처럼 그림을 그려 쉽게 확인할 수 있다. a번 학생의 키가 b번 학생의 키보다 작다면, a에서 b로 화살표를 그려서 표현하였다.1번은 5번보다 키가 작고, 5번은 4번보다 작기 때문에, 1번은 4번보다 작게 ..
문제 설명사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 번호가 부여된 평면 상의 점 n 개가 주어지며, 이 중 어느 세 점도 일직선 위에 놓이지 않는다. 매 차례 마다 플레이어는 두 점을 선택해서 이를 연결하는 선분을 긋는데, 이전에 그린 선분을 다시 그을 수는 없지만 이미 그린 다른 선분과 교차하는 것은 가능하다. 게임을 진행하다가 처음으로 사이클을 완성하는 순간 게임이 종료된다. 사이클 C는 플레이어가 그린 선분들의 부분집합으로, 다음 조건을 만족한다.C에 속한 임의의 선분의 한 끝점에서 출발하여 모든 선분을 한 번씩만 지나서 출발점으로 되돌아올 수 있다..
문제 설명N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오.https://www.acmicpc.net/problem/2812 제한 사항 풀이문제를 요약하면 길이가 N인 숫자가 주어졌을 때 K개의 숫자를 제거해 가장 큰 수를 만들면 된다. 시간을 제외하고 풀이를 생각해 보면 K개의 숫자 조합을 만들고 이를 제거해 보며 최댓값을 구하면 된다.하지만 N, K가 최대 500,000이기 때문에 시간 초과가 발생할 것이다.따라서 다른 전략이 필요하다. 우선 가장 큰 수를 만들기 위해서는 왼쪽(앞쪽)수가 커야 한다.따라서 앞에서 부터 가장 큰 수를 선택하면 된다.예를 들어 보자.4 21924 1은 앞에 아무 것도 없기 때문에 선택할 것이..
문제 설명캐슬 디펜스는 성을 향해 몰려오는 적을 잡는 턴 방식의 게임이다. 게임이 진행되는 곳은 크기가 N×M인 격자판으로 나타낼 수 있다. 격자판은 1×1 크기의 칸으로 나누어져 있고, 각 칸에 포함된 적의 수는 최대 하나이다. 격자판의 N번행의 바로 아래(N+1번 행)의 모든 칸에는 성이 있다.성을 적에게서 지키기 위해 궁수 3명을 배치하려고 한다. 궁수는 성이 있는 칸에 배치할 수 있고, 하나의 칸에는 최대 1명의 궁수만 있을 수 있다. 각각의 턴마다 궁수는 적 하나를 공격할 수 있고, 모든 궁수는 동시에 공격한다. 궁수가 공격하는 적은 거리가 D이하인 적 중에서 가장 가까운 적이고, 그러한 적이 여럿일 경우에는 가장 왼쪽에 있는 적을 공격한다. 같은 적이 여러 궁수에게 공격당할 수 있다. 공격받은..
문제 설명n×m의 0, 1로 된 배열이 있다. 이 배열에서 1로 된 가장 큰 정사각형의 크기를 구하는 프로그램을 작성하시오.0100011111100010위와 같은 예제에서는 가운데의 2×2 배열이 가장 큰 정사각형이다.https://www.acmicpc.net/problem/1915 제한 사항 풀이문제를 요약하면 주어진 2차원 배열에서 1로 만들 수 있는 최대 정사각형의 크기를 구하면 된다. 해당 문제는 완전 탐색에서 점차 발전시키면 간단하게 풀 수 있다.우선 완전 탐색으로 정답을 구하기 위해서는 모든 칸에서 시작하여 그릴 수 있을 만큼 정사각형을 그려보면 된다.0100011111100010이러한 입력이 있다고 가정해 보자.그럼 (0 ,0)은 0이기 때문에 정사각형을 그릴 수 없다.즉,..
문제 설명길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 상관없이 묶을 수 있다. 하지만, 같은 위치에 있는 수(자기 자신)를 묶는 것은 불가능하다. 그리고 어떤 수를 묶게 되면, 수열의 합을 구할 때 묶은 수는 서로 곱한 후에 더한다.예를 들면, 어떤 수열이 {0, 1, 2, 4, 3, 5}일 때, 그냥 이 수열의 합을 구하면 0+1+2+4+3+5 = 15이다. 하지만, 2와 3을 묶고, 4와 5를 묶게 되면, 0+1+(2*3)+(4*5) = 27이 되어 최대가 된다.수열의 모든 수는 단 한번만 묶거나, 아니면 묶지 않아야한다.수열이 주어졌을 때, 수열의..
문제 설명여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저의 배치는 다음 조건을 만족한다.쇠막대기는 자신보다 긴 쇠막대기 위에만 놓일 수 있다. - 쇠막대기를 다른 쇠막대기 위에 놓는 경우 완전히 포함되도록 놓되, 끝점은 겹치지 않도록 놓는다.각 쇠막대기를 자르는 레이저는 적어도 하나 존재한다.레이저는 어떤 쇠막대기의 양 끝점과도 겹치지 않는다.아래 그림은 위 조건을 만족하는 예를 보여준다. 수평으로 그려진 굵은 실선은 쇠막대기이고, 점은 레이저의 위치, 수직으로 그려진 점선 화살표는 레이저의 발사 방향이다.이러한 레이저와 쇠막대기의 배치는 다음과 같이 괄호를 이용하여 왼쪽..
문제 설명어떤 정수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 그 수를 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수가 몇 개 있는지 출력한다.https://www.acmicpc.net/problem/1016 제한 사항 풀이문제를 요약하면 min과 max사이의 수 중 제곱수로 나누어 떨어지지 않는 수의 개수를 세면 된다. 해당 문제는 에라토스테네스의 체를 응용하여 풀 수 있다.문제에서 말한 제곱 ㄴㄴ수는 소수의 조건과 유사하다.i에 제곱으로 나누어 떨어지지 않는지 확인하면 되기 때문이다.따라서 소수 판별 알고리즘은 에라토스테네스의 체를 응용하여 개수를 확인하면 된다. 2부터 시작하여 제곱..
