본문 바로가기

코딩 테스트/백준88

16932 모양 만들기 문제N×M인 배열에서 모양을 찾으려고 한다. 배열의 각 칸에는 0과 1 중의 하나가 들어있다. 두 칸이 서로 변을 공유할때, 두 칸을 인접하다고 한다.1이 들어 있는 인접한 칸끼리 연결했을 때, 각각의 연결 요소를 모양이라고 부르자. 모양의 크기는 모양에 포함되어 있는 1의 개수이다.배열의 칸 하나에 들어있는 수를 변경해서 만들 수 있는 모양의 최대 크기를 구해보자.입력첫째 줄에 배열의 크기 N과 M이 주어진다. 둘째 줄부터 N개의 줄에는 배열에 들어있는 수가 주어진다.출력첫째 줄에 수 하나를 변경해서 만들 수 있는 모양의 최대 크기를 출력한다.====문제 분석우선 초기 gr에 등록되어 있는 1들끼리 묶어준다. 이때 각각의 영역을 고유의 아이디로 등록한 뒤 해당 아이디에 대해 몇개의 1의 갯수가 등록되어.. 2025. 1. 4.
13398 연속합2 문제n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다. 또, 수열에서 수를 하나 제거할 수 있다. (제거하지 않아도 된다)예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 수를 제거하지 않았을 때의 정답은 12+21인 33이 정답이 된다.만약, -35를 제거한다면, 수열은 10, -4, 3, 1, 5, 6, 12, 21, -1이 되고, 여기서 정답은 10-4+3+1+5+6+12+21인 54가 된다.입력첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진.. 2025. 1. 4.
5557번 1학년 (자바스크립트) 문제상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀고 있다. 예를 들어, "8 3 2 4 8 7 2 4 0 8 8"에서 등식 "8+3-2-4+8-7-2-4-0+8=8"을 만들 수 있다.상근이는 올바른 등식을 만들려고 한다. 상근이는 아직 학교에서 음수를 배우지 않았고, 20을 넘는 수는 모른다. 따라서, 왼쪽부터 계산할 때, 중간에 나오는 수가 모두 0 이상 20 이하이어야 한다. 예를 들어, "8+3+2-4-8-7+2+4+0+8=8"은 올바른 등식이지만, 8+3+2-4-8-7이 음수이기 때문에, 상근이가 만들 수 없는 등식이다.숫자가 주어졌을 때,.. 2025. 1. 4.
12869 뮤탈리스크 문제수빈이는 강호와 함께 스타크래프트 게임을 하고 있다. 수빈이는 뮤탈리스크 1개가 남아있고, 강호는 SCV N개가 남아있다.각각의 SCV는 남아있는 체력이 주어져있으며, 뮤탈리스크를 공격할 수는 없다. 즉, 이 게임은 수빈이가 이겼다는 것이다.뮤탈리스크가 공격을 할 때, 한 번에 세 개의 SCV를 공격할 수 있다.첫 번째로 공격받는 SCV는 체력 9를 잃는다.두 번째로 공격받는 SCV는 체력 3을 잃는다.세 번째로 공격받는 SCV는 체력 1을 잃는다.SCV의 체력이 0 또는 그 이하가 되어버리면, SCV는 그 즉시 파괴된다. 한 번의 공격에서 같은 SCV를 여러 번 공격할 수는 없다.남아있는 SCV의 체력이 주어졌을 때, 모든 SCV를 파괴하기 위해 공격해야 하는 횟수의 최솟값을 구하는 프로그램을 작성.. 2025. 1. 3.
2133 타일 채우기 문제3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자.입력첫째 줄에 N(1 ≤ N ≤ 30)이 주어진다.출력첫째 줄에 경우의 수를 출력한다.=====문제 분석1*2, 2*1 타일들을 조합하여 세로의 길이가 3이고 가로의 길이가 n인 직사각형을 채우는 경우의 수를 출력하는 문제이다.만약 이 문제가 세로의 길이가 2였다면 가로의 길이를 인덱스로 한 배열을 선언하고 , dp[i] = dp[i-1] + dp[i-2] 가 나올 것이다.(직전 타일 가로 길이에서 타일 세로로 세워서 1개 추가하고, 두개 직전의 타일 갯수에서 가로로 눕힌 타일을 붙이니까)이 문제가 위의 경우와 다른 이유는 세로의 길이가 3이라는 것이다.가로의 길이가 홀수라면, 타일을 어떻게 채우든 빈 위치가 생겨서 답이 .. 2025. 1. 3.
2225 합분해 (자바스크립트) 문제0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오.덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다.입력첫째 줄에 두 정수 N(1 ≤ N ≤ 200), K(1 ≤ K ≤ 200)가 주어진다.출력첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다.====문제 분석0부터 N까지의 수를 여러 번 사용해서라도 조합을 만든 뒤 해당 숫자들의 합이 N이 되는 경우의 수를 출력하는 문제이다.이러한 문제는 보통 1부터 N까지의 숫자를 인덱스를 가지는 dp를 만든 뒤 dp[i][j] 를 이전 i j 들의 조합들로 점화식을 만들면 됐다. 이 문제도 처음에는 위 방식으로 dp를 만든 .. 2025. 1. 3.
30242 N-Qeen(Easy) 문제N-Queen 문제는 크기가 N×N$N \times N$인 체스판 위에 퀸 N$N$개를 서로 공격할 수 없게 놓는 문제이다. N$N$이 주어졌을 때, 퀸을 놓는 방법 한 가지를 출력하는 것은 쉽다.이 문제에서는 몇 개의 퀸이 이미 놓여있을 때, 퀸을 놓는 방법 한 가지를 출력해 보자.입력첫 번째 줄에 정수 N$N$이 주어진다. (1≤N≤20)$(1 \le N \le 20)$ 두 번째 줄에 정수 Q1$Q_1$, Q2$Q_2$, Q3$Q_3$, ⋯$\cdots$, QN$Q_N$이 주어진다. Qi$Q_i$는 i$i$번째 행에 있는 퀸의 열의 번호를 의미한다. (0≤Qi≤N)$(0 \le Q_i \le N)$ 만약 Qi$Q_i$가 0이라면 i$i$번째 행에는 퀸이 놓여있지 않다는 뜻이다.퀸이 서로 공격하는 .. 2025. 1. 2.
9663 N-Queen (자바스크립트) 문제N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.입력첫째 줄에 N이 주어진다. (1 ≤ N 출력첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다. ===문제 분석특정 위치에 퀸을 놓았을 때, 그 다음으로 퀸을 놓을 수 없는 위치를 파악하는 문제이다.만약 퀸을 2,2 에 놓았다면,1. 같은 열인 2 에는 모두 퀸을 놓을 수 없다 => 세로 선2. [0,0] [1,1] [3.3] [4,4] 에 놓을 수 없다. => 왼쪽 위에서 오른쪽 아래로 향하는 대각선3. [0,4] [1,3] [3,1] [4,0] 에 놓을 수 없다. => 오른쪽 위에서 왼쪽 아래로 향하는 대각.. 2025. 1. 2.
1931 회의실 배정 문제한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.입력첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같.. 2024. 12. 30.

티스토리툴바