![]()
문제 출저 https://www.acmicpc.net/problem/2310 2310번: 어드벤처 게임 입력은 여러 개의 미로로 주어진다. 각 미로의 첫 줄에는 미로의 방 수를 나타내는 정수 n(1 ≤ n ≤ 1000)이 주어진다. 다음 n 줄에는 각 방의 정보가 주어진다. 각 방의 정보는 방의 내용물을 나타 www.acmicpc.net 문제 어드벤처 게임을 하던 중, 1부터 n까지의 번호가 붙은 방을 지나가야 하는 마법의 미로를 마주쳤다. 각 방 안에는 번호가 붙은 문이 있을 수 있고, 각 문은 해당하는 번호의 방으로 통한다. 방 안에는 레프리콘이나 트롤이 있을 수도 있다. 레프리콘이 있는 방에 들어가면 레프리콘은 모험가의 소지금이 일정 양 이하로 떨어지지 않게 채워준다. 레프리콘은 모험가의 소지금이 ..
![]()
문제 출저 https://www.acmicpc.net/problem/16562 16562번: 친구비 첫 줄에 학생 수 N (1 ≤ N ≤ 10,000)과 친구관계 수 M (0 ≤ M ≤ 10,000), 가지고 있는 돈 k (1 ≤ k ≤ 10,000,000)가 주어진다. 두번째 줄에 N개의 각각의 학생이 원하는 친구비 Ai가 주어진다. (1 ≤ Ai ≤ 10, www.acmicpc.net 문제 풀이 문제 19학번 이준석은 학생이 N명인 학교에 입학을 했다. 준석이는 입학을 맞아 모든 학생과 친구가 되고 싶어한다. 하지만 준석이는 평생 컴퓨터랑만 대화를 하며 살아왔기 때문에 사람과 말을 하는 법을 모른다. 그런 준석이에게도 희망이 있다. 바로 친구비다! 학생 i에게 Ai만큼의 돈을 주면 그 학생은 1달간 ..
![]()
문제 출저 https://www.acmicpc.net/problem/3980 3980번: 선발 명단 각각의 테스트 케이스에 대해서, 모든 포지션의 선수를 채웠을 때, 능력치의 합의 최댓값을 한 줄에 하나씩 출력한다. 항상 하나 이상의 올바른 라인업을 만들 수 있다. www.acmicpc.net 문제 풀이 11명의 축구 선수들은 각각의 포지션의 점수가 있습니다. 11명의 선수들을 포지션을 배치했을 때 가장 큰 점수를 구해야 합니다. 백트래킹으로 풀었습니다. 모든 경우를 계산하여 가장 큰 값을 구했습니다. 소스코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util..
![]()
문제 출저 https://www.acmicpc.net/problem/15661 15661번: 링크와 스타트 첫째 줄에 N(4 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100 www.acmicpc.net 문제 풀이 백트래킹을 통해 팀을 정합니다. 각 팀의 능력치를 합해서 최소값을 구합니다. 소스 코드 package baekjoon.year24.month3.day1120.day12; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader..
![]()
문제 출저 https://www.acmicpc.net/problem/9084 9084번: 동전 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 www.acmicpc.net 문제 풀이 동전의 종류 n개와 동전으로 만들어야 할 금액 m이 주어집니다. 주어진 동전으로 금액 m을 만들 경우의 수를 구해야 합니다. DP를 통해 풀었습니다. 크기가 m+1인 1차원 배열을 만듭니다. dp = new int[m+1] 이 dp 배열은 0부터 m까지 금액을 만들 수 있는 경우의 수를 저장합니다. dp[0] 인 0원은 동전을 하나도 안 사용하는 방법만 있으니..
![]()
문제 출저 https://www.acmicpc.net/problem/13398 13398번: 연속합 2 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 문제 풀이 수열에서 연속하는 몇 개의 수를 선택해 가장 큰 합을 구해야 한다. 이 때, 한 개의 수는 선택하지 않아도 된다. DP를 이용하여 문제를 풀었습니다. 다만 숫자를 하나 뺄 때, 빼지 않을 때 2가지 경우의 수를 염두해야 합니다. dp = new int[n][2]; 0은 빼지 않았을 경우, 1은 뺀 경우입니다. dp[n][0] 일 때는 뻰 경우 입니다. 전의 값(i - 1)과 수열..
![]()
문제 출저 https://www.acmicpc.net/problem/1940 1940번: 주몽 첫째 줄에는 재료의 개수 N(1 ≤ N ≤ 15,000)이 주어진다. 그리고 두 번째 줄에는 갑옷을 만드는데 필요한 수 M(1 ≤ M ≤ 10,000,000) 주어진다. 그리고 마지막으로 셋째 줄에는 N개의 재료들이 가진 고 www.acmicpc.net 문제 풀이 재료들의 번호가 주어집니다. 재료들의 고유 번호를 합쳐서 M이 되는 경우의 수를 구해야 합니다. 두 포인터를 이용해 풀었습니다. 재료들을 정렬합니다. start, end 두 개의 포인터를 사용합니다. start는 배열의 시작, end는 배열의 끝에서 시작합니다. 두 개의 합을 합쳐서 M 보다 작으면 start를 올리고 M보다 크면 end를 줄입니다. ..
![]()
문제 출저 https://www.acmicpc.net/problem/16472 16472번: 고냥이 고양이는 너무 귀엽다. 사람들은 고양이를 너무 귀여워했고, 결국 고양이와 더욱 가까워지고 싶어 고양이와의 소통을 위한 고양이 말 번역기를 발명하기로 했다. 이 번역기는 사람의 언어를 고 www.acmicpc.net 문제 풀이 인식할 수 있는 알파벳의 종류 n과 문자열이 주어집니다. 문자열에서 인식할 수 있는 최대의 길이를 구해야 합니다. 투 포인터를 이용해 풀었습니다. 어떤 알파벳이 몇 개 나왔는지 세기 위한 int[] counts = new int[26]; 일차원 배열을 이용했습니다. 알파벳 갯수는 26개 이므로 배열의 크기를 26으로 설정했습니다. int start = 0, int end = 1 인 두..
![]()
문제 출저 https://www.acmicpc.net/problem/20366 20366번: 같이 눈사람 만들래? 높이가 (2, 5), (3, 5)로 구성된 눈사람 둘을 만드는 것이 최적의 경우 중 하나이다. |7-8| = 1 다른 경우로는 (2, 9), (5, 5)로 두 눈사람을 만드는 경우가 있다. |11-10| = 1 www.acmicpc.net 문제 풀이 N개의 눈덩이가 주어집니다. 언니 엘자와 동생 안나는 각각 두 개의 눈덩이를 선택합니다. 눈 사람의 크기는 두 개의 눈덩이 지름의 합입니다. 두 사람의 눈사람 크기 차이가 최소일 경우를 구해야합니다. N의 크기는 4이상 600이하 입니다. 이중 포문과 투 포인터로 문제를 풀었습니다. 이중 포문으로 눈덩이 2개를 골랐습니다. 2개의 나머지 부분을 ..
![]()
문제 출저 https://www.acmicpc.net/problem/14921 14921번: 용액 합성하기 홍익대 화학연구소는 다양한 용액을 보유하고 있다. 각 용액은 -100,000,000부터 100,000,000사이의 특성 값을 갖는데, 같은 양의 두 용액을 혼합하면, 그 특성값은 두 용액의 특성값의 합이 된다. 당신 www.acmicpc.net 문제 풀이 -100,000,000 ~ 100,000,000 값을 갖는 용액이 n개 주어집니다. 두 개 용액을 섞어 0에 가장 가까운 값이 무엇인지 구해야 합니다. 투 포인터로 문제를 풀었습니다. int[] liquors 용액 배열에 입력값을 받습니다. Arrays.sort() 메소드를 통해 liquors int 배열을 정렬합니다. 처음과 끝은 두 개의 포인터..
![]()
문제 출저 https://www.acmicpc.net/problem/1484 1484번: 다이어트 성원이는 다이어트를 시도중이다. 성원이는 정말 정말 무겁기 때문에, 저울이 부셔졌다. 성원이의 힘겨운 다이어트 시도를 보고만 있던 엔토피아는 성원이에게 새로운 저울을 선물해 주었다. www.acmicpc.net 문제 풀이 성원이는 다이어트 중이다. 성원이의 현재 몸무게의 제곱 - 기억하는 몸무게의 제곱 = G 이다. 이 때 G를 만족하는 현재 몸무게를 구해야 한다. 투 포인터를 이용해 풀었습니다. long e : 현재 몸 무게 long s : 기억하는 몸 무게 이렇게 두 개의 포인터를 사용하여 e*e - s*s
![]()
문제 출저 https://www.acmicpc.net/problem/20922 20922번: 겹치는 건 싫어 홍대병에 걸린 도현이는 겹치는 것을 매우 싫어한다. 특히 수열에서 같은 원소가 여러 개 들어 있는 수열을 싫어한다. 도현이를 위해 같은 원소가 $K$개 이하로 들어 있는 최장 연속 부분 수열 www.acmicpc.net 문제 풀이 수열이 주어질 때, 같은 정수를 K개 이하로 포함한 최장 연속 부분 수열의 길이를 구해야 한다. 투 포인터로 문제를 풀었습니다. end, start를 두 개의 포인터를 이용했습니다. end, start는 모두 0에서 시작합니다. end는 배열의 끝까지 탐색합니다. end 포인터에 걸린 숫자의 갯수를 +1 해줍니다. 만약 숫자의 갯수가 K보다 크다면 start가 움직입니다..
