https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 문제 요약 입력으로 N과 N*N 배열에 들어가는 능력치가 주어진다. N/2명씩 스타트 팀, 링크 팀을 만들어서 팀에 속한 팀원끼리 만나면 발휘되는 능력치를 더하고, 두 팀의 능력치가 최소가 되는 값을 출력한다. 문제 해결 아이디어 당연히 처음에는 nCn/2의 문제라고 생각했다. 하지만 순열 조합 부분집합을 재귀로 구하는 문제의 쟁점은 가지치기! 즉 어떻게 최소한으로 돌릴 것인가를 생각해 봐야 한다. 생각해 보니 만약 ..
https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 문제 요약 상담원은 오늘부터 N+1째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다. 매일매일 상담을 잡아 놓았지만 상담마다 완료하는 데 걸리는 기간과 받을 수 있는 금액이 다르다. 1일에 하는 상담이 3일 걸린다면, 4일부터 또 다른 상담이 가능하다. 이런 경우에 N일 동안 상담원이 얻을 수 있는 최대 수익은? 문제 해결 아이디어 먼저 입력받은 상담을 선택하느냐, 하지 않느냐 두 가지의 선택지가 있는 것이라고 생각하고 부분집합으로 풀겠다는 아이디어를 떠올렸다. 하지만 단순 부분집합은 아니고, 상담마다..
https://www.acmicpc.net/problem/9012 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net 문제 요약 한 쌍의 괄호 기호로 된 "()" 문자열을 VPS라고 부른다. 입력으로 주어진 괄호 문자열이 VPS인지 아닌지를 판단해서 그 결과를 YES와 NO로 나타낸다. 문제 해결 아이디어 stack을 이용한다. stack이 비어있으면 무조건 넣고, 비어있지 않을 때에는 stack.peek(), 즉 가장 최근에 들어간 괄호가 현재 괄호와 같은지 확인 후 같으면 넣고,..
https://www.acmicpc.net/problem/2447 2447번: 별 찍기 - 10 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 www.acmicpc.net 문제 요약 재귀적인 패턴으로 별을 찍어 보자. 입력되는 N은 3의 거듭제곱이고, 출력되는 패턴은 공백으로 채워진 가운데의 (N/3)*(N/3) 정사각형을 크기 N/3의 패턴으로 둘러싼 형태이다. 문제 해결 아이디어 크게 보면 계속해서 3*3의 반복을 돌면 된다. 그러면서 가운데는 비워주고, 가운데가 아니라면 계속해서 옆으로 밑으로 보내서 N==1이 되는 순간 별을 찍을 ..
https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 문제 요약 정수 n이 주어졌을 때 그 수를 1, 2, 3의 합으로 나타내는 방법의 수를 구하시오. 문제 해결 아이디어 하나하나 노가다로 구해 본 결과.... ㅎ recursive(n) = recursive(n-1)+recursive(n-2)+recursive(n-3)란 결과를 구할 수 있었다. 완성된 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class M..
https://www.acmicpc.net/problem/2503 2503번: 숫자 야구 첫째 줄에는 민혁이가 영수에게 몇 번이나 질문을 했는지를 나타내는 1 이상 100 이하의 자연수 N이 주어진다. 이어지는 N개의 줄에는 각 줄마다 민혁이가 질문한 세 자리 수와 영수가 답한 스트 www.acmicpc.net 문제 요약 정답과 위치, 숫자까지 같으면 스트라이크이고, 위치는 다르지만 같은 숫자가 있으면 볼이다. 서로 다른 세 자리 수를 원하는 만큼 입력받고, 그에 대한 스트라이크와 볼 갯수를 입력받는다. 원하는 만큼 입력받았을 때 정답이 될 수 있는 숫자의 개수를 출력한다. 문제 해결 아이디어 1부터 9까지의 숫자 중 서로 다른 3자리 수를 뽑는 것은 9P3이므로 전체 경우의 수가 크지 않기 때문에 모든..
https://www.acmicpc.net/problem/2309 2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net 문제 요약 9명의 난쟁이 키가 입력으로 주어지면, 합이 100이 되는 일곱 난쟁이를 찾아내야 한다. 문제 해결 아이디어 입력 크기가 크지 않으므로 모든 경우를 검사해 보는 완전탐색 기법을 생각했다. 9명 중에 7명을 뽑는다. 순서는 중요하지 않기 때문에 조합으로 생각했다. 뽑힌 7명의 합을 구해 100과 비교한다 100이면 출력 완성된 코드 import java.io.BufferedReader; impor..
