기록방

👉 문제링크 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 🔸 문제 분석 🔸 N명 중에서 N/2명을 뽑았을때 나오는 시너지 차이의 최소값을 출력한다. N명에서 N/2를 뽑는 조합 문제이다. 반대 팀으로 뽑히면 같은 값을 중복으로 검사하게 되지만, 시간복잡도가 허용범위 내이므로 감안해도 된다. 조합으로 뽑아 시너지 차이의 최소값을 업데이트한다. 🔸 코드 🔸 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import..

👉 문제링크 2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다 www.acmicpc.net 🔸 문제 분석 🔸 9 x 9 스도쿠의 빈칸을 채우는 문제이다. 스도쿠는 가로, 세로, 소속 3x3 칸에 중복되는 숫자가 없어야 한다. 여러 개의 답 중 사전식으로 앞서는 것을 출력한다. 그리디하게 접근해서 좌상단부터 우하단으로 넣을 수 있는 작은 수들을 넣다보면 넣을수 없는 경우가 생긴다. 따라서 넣을 수 없는 경우는 다시 돌아가서 다음 숫자를 넣어봐야 하므로 백트래킹을 사용한다. 🔸 코드 🔸 import java.io.BufferedReade..

👉 문제링크 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 🔸 문제 분석 🔸 N개의 도시에서 모든 도시를 방문하고 마지막에 출발지로 돌아오는 여행 경로 중 가장 적은 비용을 출력한다. 재귀와 백트래킹을 통해 구현한다. 🔸 코드 🔸 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public..

👉 문제링크 6987번: 월드컵 월드컵 조별 최종 예선에서는 6개국으로 구성된 각 조별로 동일한 조에 소속된 국가들과 한 번씩, 각 국가별로 총 5번의 경기를 치른다. 조별리그가 끝난 후, 기자가 보내온 각 나라의 승, 무승부 www.acmicpc.net 🔸 문제 분석 🔸 월드컵에서 6개의 국가가 서로 1번씩 경기를 뛰고 나온 결과로 가능한지 불가능한지 판단한다. 4번의 경기 결과가 주어지는데, 한 나라의 승, 무, 패의 수로 입력된다. 가능한 결과이면 1, 불가능한 결과이면 0을 반환한다. 6개의 국가에서 경기를 뛰는 경우의 수는 6C2 = 6*5/2 = 15개 이다. 승/무/패 상관없이 총 15번의 경기가 가능하면, 올바른 경기 결과이다. 입력 제한이 0~6 이므로, 한 국가의 승무패의 합이 5가 되..

👉 문제링크 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 🔸 문제 분석 🔸 고정된 위치의 숫자와, 그 사이에 하나 씩 들어갈 수 있는 4종류의 연산자들의 개수가 주어진다. 계산으로 만들 수 있는 값의 최대값과 최소값을 출력한다. 연산자 자리를 바꾸면 값이 달라지기 때문에 순열로 풀이할 수 있다. 같은 종류의 연산자는 자리를 바꿔도 중복계산이기 때문에 dfs나 nextpermutation으로 중복을 제거할 수 있다. 🔸 순열 🔸 import java.io..