문제 https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 풀이 주어진 연산자들의 순열을 순차적으로 탐색하며 최솟값과 최댓값을 찾는다. 연산자들의 다음 순열을 찾아 나가므로, 연산자 배열을 string이 아닌 int 배열로 만든다. 숫자 n개가 주어질 때, 연산자의 총 개수는 n-1개이므로, 연산자 배열의 길이는 n-1이다. +를 0, -를 1, x를 2, %를 3으로 하여 연산자 배열에 저장한..

문제 https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 풀이 주어진 두 단어의 알파벳을 숫자로 바꾸어 더했을 때의 최댓값을 구하는 문제이다. 만약, ABCDE와 FGH를 더할 때, 각 알파벳에 어떤 숫자가 오든지간에 ABCDE가 더 큰 숫자가 된다. 단어의 길이가 더 길다면, 더 높은 자릿수의 숫자이기 때문이다. 이런 경우, 같은 자릿수를 가지는 CDE와 FGH를 제외하고, 더 높은 자릿수인 A와 B에 큰 수 9와 8을 배치할 것이다. 그리..

문제 https://www.acmicpc.net/problem/2529 2529번: 부등호 두 종류의 부등호 기호 ‘’가 k개 나열된 순서열 A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제시 www.acmicpc.net 풀이 백트래킹 방법으로 문제를 해결할 것이다. 백트래킹 방법은 가지를 탐색하다가 옳지 않으면 바로 다른 가지로 넘어간다. 이 문제에서는 첫번째 자리의 수부터 k+1번째 자리의 수까지 추가해나가며 탐색한다. 탐색 중에 j번째 자리에 넣을 수가 이전 수와의 부등호 조건에 맞지 않으면(ex- 부등호가

문제 https://www.acmicpc.net/problem/2529 2529번: 부등호 두 종류의 부등호 기호 ‘’가 k개 나열된 순서열 A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제시 www.acmicpc.net 풀이 부등호가 k개 존재할 때, 부등호 앞 뒤로 숫자가 들어가게 되므로 숫자는 k+1개가 놓일 것이다. 어떤 부등호가 k개 쓰이든지 간에, k+1개의 숫자가 최대가 되려면 0부터 9까지의 정수 중 큰 k+1개의 정수만이 쓰여야 한다. 반대로, 최소가 되려면, 작은 k+1개의 정수만이 쓰여야 한다. ① 최댓값을 찾는 방법 가장 큰 수부터 시작하여 점점 작은 수를 탐색한다. 따라서 현재의 순열이 부등호의 조..

문제 https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 풀이 사다리가 있는 위치라면 사다리를 타고 올라갈 위치가 존재하고, 뱀이 있는 위치라면 뱀을 타고 내려갈 위치가 존재한다. 사다리와 뱀이 있는 위치와, 이동할 위치를 해시맵으로 저장한다. ladder = new HashMap(); //사다리와 이동 위치 저장할 해시맵 snake = new HashMap(); //뱀과 이동 위치 저장할 해시맵 fo..

문제 https://www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 숨바꼭질(1697번) 문제와 유사하다. 다른 점이 있다면, 숨바꼭질4에서는 둘째 줄에 경로도 출력해야 한다는 점이다. 이 경우도 BFS로 풀 수 있다. 숨바꼭질 문제에 대한 BFS 풀이를 아래 글에서 확인해보고 오자. 2023.01.13 - [문제풀이/BFS] - [백준/JAVA] 1697번 : 숨바꼭질(BFS) [백준/JAVA] 1697번 : 숨바꼭질..