![]()
문제 출저 https://www.acmicpc.net/problem/1935 1935번: 후위 표기식2 첫째 줄에 피연산자의 개수(1 ≤ N ≤ 26) 가 주어진다. 그리고 둘째 줄에는 후위 표기식이 주어진다. (여기서 피연산자는 A~Z의 영대문자이며, A부터 순서대로 N개의 영대문자만이 사용되며, 길이 www.acmicpc.net 문제 풀이 후위 표기식이 주어지고 알파벳의 숫자가 주어집니다. 이 정보를 통해 후위 표기식을 계산한 정답을 구해야 합니다. Stack, Map을 활용하여 문제를 풀었습니다. Map으로 알파벳별 숫자를 저장합니다. 후위 표기식에 하나씩 탐색을 합니다. 알파벳이 나올 경우 Map을 통해서 해당되는 알파벳의 double 값을 stack에 저장합니다. +, -. *, / 연산자가 나..
![]()
문제 출저 https://www.acmicpc.net/problem/5076 5076번: Web Pages Input will consist of a number of lines of HTML code, each line containing from 0 to 255 characters. The last line will contain a single # character – do not process this line. Within the text of each line will be zero or more tags. No angle bracket will www.acmicpc.net 문제 풀이 String이 #이 나올 때까지 주어집니다. String이 HTML 태그 형식에 맞는지 확인해서 옳다면 leg..
![]()
문제 출저 https://www.acmicpc.net/problem/2346 2346번: 풍선 터뜨리기 1번부터 N번까지 N개의 풍선이 원형으로 놓여 있고. i번 풍선의 오른쪽에는 i+1번 풍선이 있고, 왼쪽에는 i-1번 풍선이 있다. 단, 1번 풍선의 왼쪽에 N번 풍선이 있고, N번 풍선의 오른쪽에 1번 풍선 www.acmicpc.net 문제 풀이 풍선의 갯수와 풍선 안에 숫자가 주어집니다. 풍선 안에 숫자는 양수와 음수로 양수면 오른쪽부터 세고, 음수면 왼쪽으로 셉니다. 셈을 마친 풍선을 터뜨리고 해당 풍선의 숫자만큼 반복합니다. 1번부터 풍선을 터뜨렸을 때, 어떤 순서로 풍선들이 터지는지 구해야 합니다. Deque를 이용해 문제를 풀었습니다. 양수인 경우 해당 숫자만큼 처음에서 빼서 끝에 넣었습니다..
![]()
문제 출저 https://www.acmicpc.net/problem/7490 7490번: 0 만들기 각 테스트 케이스에 대해 ASCII 순서에 따라 결과가 0이 되는 모든 수식을 출력한다. 각 테스트 케이스의 결과는 한 줄을 띄워 구분한다. www.acmicpc.net 문제 풀이 테스트 케이스 t가 주어지고 t번 만큼 숫자 n이 주어집니다. 1부터 n까지 차례대로 숫자를 사용하고 숫자 사이에 +. -. " "(공백)을 넣어 수식을 완성합니다. 공백은 숫자 2개를 붙인다는 의미 입니다. (2 3 => 23) 수식을 완성하고 계산했을 때, 0이 되는 수식을 구해야 합니다. dfs를 이용해 전체 수식의 경우의 수를 구했습니다. 수식은 공백을 붙이기 위해 String으로 구했습니다. String의 replace..
![]()
문제 출저 https://www.acmicpc.net/problem/1722 1722번: 순열의 순서 첫째 줄에 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄의 첫 번째 수는 소문제 번호이다. 1인 경우 k(1 ≤ k ≤ N!)를 입력받고, 2인 경우 임의의 순열을 나타내는 N개의 수를 입력받는다. N개의 수에는 1부터 N www.acmicpc.net 문제 풀이 이 문제는 2가지 문제를 풀어야 합니다. 첫 번째 입력은 n이 주어지고 두 번째 입력의 첫 번째 숫자는 어떤 문제를 풀어야 하는지 타입입니다. 1인 경우, k가 주어지며 k번째 순열을 구해야 합니다. 2인 경우, 순열이 주어지며 이 순열이 몇 번째 순서인지 구해야 합니다. 문제의 n은 20이므로 일일히 다 순열을 구하면 20! 이 되므로 시간초과..
![]()
문제 출저 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 문제 풀이 주사위를 굴려 1부터 시작해서 100번째 칸에 가려합니다. 이 때, 주사위는 원하는 숫자를 뽑을 수 있고 칸에는 사다리와 뱀이 있습니다. 사다리는 낮은 숫자에서 높은 숫자로 이동하고 반대로 뱀은 높은 숫자에서 낮은 숫자로 이동합니다. 사다리와 뱀의 정보가 주어질 때, 100번째 칸으로 가기 위한 주사위를 굴리는 최소 횟수를 구해야..
![]()
문제 출저 https://www.acmicpc.net/problem/15990 15990번: 1, 2, 3 더하기 5 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 문제 풀이 테스트 케이스 t가 주어집니다. t의 수 만큼 n이 주어질 때, 1,2,3을 더해서 n을 만들 경우의 수를 구해야 합니다. 이 때 연속으로 같은 수가 오면 안됩니다. 경우의 수에 1_000_000_009의 나머지 값을 구해야 합니다. dp로 문제를 풀었습니다. n의 범위는 100_000 입니다. dp[100_001][4] 2차원 배열을 만들었습니다. dp[n][1] 이것은 n번째 수의 1로 끝나는 경우의 수 입니다. n의 모든..
![]()
문제 출저 https://www.acmicpc.net/problem/12852 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net 문제 풀이 숫자가 주어졌을 때, 3이나 2로 나누어 떨어지면 나눌 수 있고 -1을 할 수 있다. 이런 식으로 연산을 거쳐 1을 만들 때 최소한 연산 횟수와 그 과정을 구해야 합니다. DP를 이용해서 풀었습니다. 처음에 BFS로 Queue를 이용하고 이미 방문한 곳이 횟수가 적으면 가지치기를 하는 방식으로 풀었는데 시간 초과가 발생했습니다. 1차원 배열과 메모리제이션으로 코드를 바꿔서 문제를 풀었습니다. 문제를 풀기 위해 dot 클래스를 새로 만들었습니다. dot 클래스는 횟수를 저장하는 co..
![]()
문제 출저 https://www.acmicpc.net/problem/2631 2631번: 줄세우기 KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 www.acmicpc.net 문제 풀이 번호를 가진 아이들이 있습니다. 이 아이들을 번호 순서대로 줄을 세우려 할 때 이동해야 하는 최소한의 갯수를 구해야 합니다. DP를 이용해 풀었습니다. 이동해야 하는 최소 갯수는 오름차순이 되지 않은 숫자들의 갯수 입니다. 예제의 경우를 보면 3 7 5 2 6 1 4 인데 이 때 가장 긴 오름차순의 길이는 3 5 6 으로 3 입니다. 그러면 나머지 숫자들의 자리를 바꿔주면 되므로 정..
![]()
문제 출저 https://www.acmicpc.net/problem/18405 18405번: 경쟁적 전염 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치 www.acmicpc.net 문제 출저 2차원 배열에 바이러스가 숫자로 부여됩니다. 바이러스는 1초에 상하좌우로 퍼지고 이미 바이러스가 있다면 퍼지지 않습니다. s 초 후, (x,y) 좌표에 어떤 바이러스가 있는지 구해야 합니다. 구현으로 문제룰 플었습니다. dot 클래스를 만들어 x,y,count 좌표를 만들었습니다. List virus 자료형을 만들어 바이러스 번호대로 위치를 저장..
![]()
문제 출저 https://www.acmicpc.net/problem/20002
![]()
문제 출저 https://www.acmicpc.net/problem/2075 2075번: N번째 큰 수 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. www.acmicpc.net 문제 풀이 n이 주어지며 n*n의 2차원 배열로 된 숫자들이 주어집니다. 이 때 이 숫자들 중 n번째로 큰 숫자를 구해야 합니다. 우선수위 큐를 이용해 풀었습니다. 2차원 배열의 숫자들을 우선순위 큐에 넣어 n번째 큰 숫자를 구했습니다. 소스 코드 package baekjoon.backjoon11.day0110.day01; import java.io.BufferedReader; import j..
