https://www.acmicpc.net/problem/10819 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net 문제 요약 N개의 정수가 들어 있는 배열이 입력된다. 다음 식의 최댓값을 구하는 프로그램을 작성하시오. |A[0] - A[1]| + |A[1] - A[2]| + ... + |A[N-2] - A[N-1]| 문제 해결 아이디어 배열의 크기가 크지 않으므로 모든 순서를 다 조합해서 최댓값을 찾는다. 후보의 순서가 중요하기 때문에 순열으로 뽑는다. 완성된 코드 package week3; import java.io.Bu..
https://www.acmicpc.net/problem/20055 20055번: 컨베이어 벨트 위의 로봇 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부 www.acmicpc.net 문제 요약 길이가 2N인 벨트가 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 1번 칸이 있는 위치는 "올리는 위치", N번 칸이 있는 위치는 "내리는 위치"이다. 컨베이어 벨트에 박스 모양 로봇을 하나씩 올리려고 한다. 로봇은 올리는 위치에만 올릴 수 있고, 내리는 위치에 도달하면 그 즉시 내린다. 로봇을 올리는 위치에 올리거나 어떤 칸으로 이동하면 내구도는 1만큼 감소한다...
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이므로 전체 경우의 수가 크지 않기 때문에 모든..