문제 출저 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..
문제 출저 https://www.acmicpc.net/problem/15989 15989번: 1, 2, 3 더하기 4 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 4가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 합을 이루고 있는 수의 순서만 다른 것은 같은 것으로 친다. 1+1+1+1 2+1+1 (1+1+2, 1+2+1) 2+2 www.acmicpc.net 문제 풀이 숫자가 주어졌을 때, 1,2,3 을 더하여 숫자를 만들 수 있는 경우의 수를 구해야 합니다. DP를 이용하여 풀었습니다. 점화식을 세우는게 중요합니다. 합을 이루고 있는 수의 순서만 다른 것은 같은 것으로 칩니다. 이 때문에 수식을 오름차순으로 만들었습니다. int[][] dp 2차원 int 배열을 만들었습니다. ..
문제 출저 https://www.acmicpc.net/problem/25682 25682번: 체스판 다시 칠하기 2 첫째 줄에 정수 N, M, K가 주어진다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 문제 풀이 검은색과 흰 색으로 칠해진 n, m 크기의 판이 주어집니다. 변인 k인 정사각형으로 자릅니다. 이 정사각형을 올바른 체스판으로 만들기 위해서 색칠을 칠해야 할 때 최소한의 칠하는 횟수를 구해야 합니다. 누적합으로 풀었습니다. 체스판은 2가지 경우가 있습니다. 왼쪽 위가 검은색이거나 흰색일 경우 입니다. 2가지 상황에 맞는 누적합 배열을 구해서 모든 경우의 수를 비교하여 최소값을 구했습니다. 소스 코드 package ..
문제 출저 https://www.acmicpc.net/problem/12847 12847번: 꿀 아르바이트 월세를 내기 바로 전 날 까지 인 n (1 ≤ n ≤ 100,000) 일과 일을 할 수 있는 날 m (0 ≤ m ≤ n) 일이 주어진다. 그 다음 줄 에는 1일부터 n일 까지 일급 Ti가 순서대로 주어진다. (0 < Ti ≤ 1,000,000) www.acmicpc.net 문제 풀이 전체 기간 n과 일을 할 수 있는 기간 m이 주어집니다. 이 때, 최대한 많은 돈을 버는 경우를 구해야 합니다. 누적합으로 풀었습니다. 1차원 배열 long[] prefix를 만들고 탐색을 통해 최대의 돈을 구했습니다. 범위가 크기 때문에 int가 아닌 long 자료형을 사용했습니다. 소스 코드 package baekj..
문제 출저 https://www.acmicpc.net/problem/16139 16139번: 인간-컴퓨터 상호작용 첫 줄에 문자열 $S$가 주어진다. 문자열의 길이는 $200,000$자 이하이며 알파벳 소문자로만 구성되었다. 두 번째 줄에는 질문의 수 $q$가 주어지며, 문제의 수는 $1\leq q\leq 200,000$을 만족한다. 세 번째 www.acmicpc.net 문제 풀이 문자열이 주어지고 알파벳과 구간의 시작과 끝을 q번 주어집니다. 이 떄, 시작과 끝 구간에 알파벳의 갯수를 구해야 합니다. 누적합을 통해 풀었습니다. 문자열이 주어졌을 때, a~z 까지의 각각의 알파벳에 해당하는 2차원 배열의 누적합을 만들었습니다. 이 누적합 배열을 이용하여 정답을 구했습니다. 소스 코드 package bae..
문제 출저 https://www.acmicpc.net/problem/10986 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 문제 풀이 수 N개가 주어집니다. 이 떄 연속된 부분 구간 합이 M으로 나누어 떨어지는 구간의 개수를 구해야 합니다. 누적합으로 풀었습니다. int[] prefix 라는 1차원 정수 배열로 누적합을 만들었습니다. int[] remainder 라는 1차원 정수 배열로 누적합을 m으로 나눈 나머지의 갯수를 저장했습니다. 그 누적합의 갯수를 이..
문제 출저 https://www.acmicpc.net/problem/16938 16938번: 캠프 준비 난이도가 10, 30인 문제를 고르거나, 20, 30인 문제를 고르면 된다. www.acmicpc.net 문제 풀이 난이도가 있는 문제 n개가 주어집니다. 2개 이상의 문제를 선택해야 합니다. 그 중, 문제난이도의 합이 L 이상, R 이하, 선택 된 문제 중 최대 난이도 - 최소 난이도가 X 이상인 경우의 수를 구해야 합니다. DFS를 이용해 경우의 수를 구하는 걸로 문제 풀었습니다. 탐색할 때 문제의 합이 R보다 크면 탐색을 중단했습니다. 문제를 풀 때 최소값을 구할 때 초기값을 잘 못 설정하여 0%에서 계속 틀렸습니다. 최소값의 초기값을 Integer.MAX_VALUE로 두어 문제를 해결했습니다. ..
문제 출저 https://www.acmicpc.net/problem/1911 1911번: 흙길 보수하기 어젯밤 겨울 캠프 장소에서 월드 본원까지 이어지는, 흙으로 된 비밀길 위에 폭우가 내려서 N(1 ≤ N ≤ 10,000)개의 물웅덩이가 생겼다. 월드학원은 물웅덩이를 덮을 수 있는 길이가 L(1 ≤ L ≤ 1,000 www.acmicpc.net 문제 풀이 웅덩이 n개, 판자의 길이 l 이 주어집니다. 웅덩의 시작과 끝이 주어질 때 몇 개의 판자로 웅덩이를 모두 막을 수 있는지 구해야 합니다. 정렬과 구현으로 문제를 풀었습니다. 웅덩의 시작 지점, 끝 지점으로 오름차순으로 이중 정렬을 했습니다. 그 다음은 int range 변수를 설정해서 판자를 표시했습니다. 시작지점부터 시작해서 while 문으로 계속..
문제 출저 https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 문제 풀이 학생들과 학생들이 선호하는 학생이 1차원 배열로 주어집니다. 이 때 서로를 가리키다 사이클이 완성되면 팀을 이루게 됩니다. 팀을 이루지 못한 학생들이 몇 명인지 구하는게 문제의 요구사항입니다. dfs와 방문 처리로 문제를 풀었습니다. visited와 finished라는 boolean 배열을 만들었습니다. visited : 사이클을 이루는 구성원인지 판단 finished : 이미 탐..
문제 출저 https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 문제 풀이 세로 n, 가로 m인 2차원 배열이 주어지고 (1,1)에서 (n,m)으로 가야 합니다. 2차원 배열에는 벽이 1로 주어집니다. 이 때 최(n,m)으로 가기 위해 부숴야하는 최소한의 벽의 갯수를 구하는게 이 문제의 요구 사항 입니다. DP와 BFS로 풀었습니다. BFS로 Queue를 만들어 (1,1)을 시작점으로 하여 4방향 탐색을 시작했습니다. 2차원 d..
문제 출저 https://www.acmicpc.net/problem/2167 2167번: 2차원 배열의 합 첫째 줄에 배열의 크기 N, M(1 ≤ N, M ≤ 300)이 주어진다. 다음 N개의 줄에는 M개의 정수로 배열이 주어진다. 배열에 포함되어 있는 수는 절댓값이 10,000보다 작거나 같은 정수이다. 그 다음 줄에는 www.acmicpc.net 문제 풀이 숫자가 있는 2차원 배열이 주어집니다. 이 때, 범위가 주어지는데 범위에 포함된 숫자들의 합을 구하는 것이 문제의 요구사항 입니다. 누적합으로 풀었습니다. prefix 2차원 배열을 만들어 i,j 지점에 0.0 부터 i,j 까지의 모든 숫자를 더한 값을 저장합니다. 그 후, 누적합 배열을 이용해 수식을 만들어 정답을 구했습니다. 소스 코드 pack..
문제 출저 https://www.acmicpc.net/problem/1743 1743번: 음식물 피하기 첫째 줄에 통로의 세로 길이 N(1 ≤ N ≤ 100)과 가로 길이 M(1 ≤ M ≤ 100) 그리고 음식물 쓰레기의 개수 K(1 ≤ K ≤ N×M)이 주어진다. 그리고 다음 K개의 줄에 음식물이 떨어진 좌표 (r, c)가 주어진다 www.acmicpc.net 문제 풀이 음식물 쓰레기 위치가 주어졌을 때, 가장 큰 덩어리의 크기를 구하는게 문제입니다. 저는 BFS를 통해서 풀었습니다. 2차원 배열을 하나씩 탐색하면 음식물 쓰레기면 BFS를 통해서 덩어리를 구했습니다. 이를 통해 가장 큰 덩어리를 구했습니다. 소스 코드 package baekjoon.backjoon10.day1120.day18; impo..
