0과 1의 쉼터

[백준 15688] 수 정렬하기 5 [Java]

문제https://www.acmicpc.net/problem/15688풀이처음 풀어보는 시간 누적 유형의 문제다.문득 궁금한건 TC의 전체 수가 공개되지 않았는데 어떤 기준으로 시간 제한에 걸리지 않게 푸는지 이해하지 못했다.일단은 기존에 작성한 코드를 최대한 효율적으로 변경했다.2025.01.08 - [PS/Baekjoon Online Judge] - [백준 11931] 수 정렬하기 4 [Java] [백준 11931] 수 정렬하기 4 [Java]문제https://www.acmicpc.net/problem/11931풀이N개의 수를 입력받아 내림차순으로 정렬 후 출력하면 된다.우선 입력을 받고,내림차순 정렬 후순회하며 StringJoiner에 담아도 되고, 정규표현식을 사용해 간단kyr-db.tistory..

문제https://www.acmicpc.net/problem/11931풀이N개의 수를 입력받아 내림차순으로 정렬 후 출력하면 된다.우선 입력을 받고,내림차순 정렬 후순회하며 StringJoiner에 담아도 되고, 정규표현식을 사용해 간단히 출력해도 된다.소스코드보기

문제https://www.acmicpc.net/problem/2294풀이N가지 종류의 동전이 주어질 때, 동전의 합이 K가 되는 최소 개수를 구하는 문제다.N은 최대 100이므로, 모든 동전에 대해 K를 만들어보는 경우를 전부 계산해볼 수 있다.dp[i] : 현재까지 살펴본 동전들로 i원을 만들기 위한 최소 개수우선 K의 최대는 10,000이므로 dp를 10,001, dp[0] = 0으로 초기화하자.이제 입력받은 동전에 대해 최소 동전 개수를 갱신하면 된다.범위 coin ~ K에 대해 현재 동전의 액수를 뺀 기록( dp[i - coin] )에 현재 동전 더하는 수가 적은 경우로 갱신해주면 된다. 만약 dp[K]가 초기값인 10,001이라면 K를 만드는 경우의 수가 존재하지 않는 경우이므로 -1을 출력하자..

문제https://www.acmicpc.net/problem/32978풀이입력받은 N개의 재료에 대해 언급되지 않은 재료를 찾는 문제다.우선 N개의 재료를 입력받아 집합에 넣어주자.다음으로 N - 1개의 재료를 입력받아 어떤 재료가 빠졌는지 확인하면 된다.입력받은 재료들을 집합에서 제거해주자.정확히 N개를 입력받고, N - 1개를 제거했으므로 집합의 첫 번째 요소를 출력하면 된다.소스코드보기

문제https://www.acmicpc.net/problem/1520풀이최대 500 X 500 크기의 보드에 대해 상하좌우 움직이면서 이전 위치보다 숫자가 작은 방향으로만 움직여 왼쪽 위에서 오른쪽 아래로 도착하는 경우의 수를 구하는 문제다.단순히 그래프 탐색으로 모든 경우의 수를 탐색하면 시간초과가 발생한다.중복 방문을 하지 않으면서도, 모든 경우의 수를 계산해야 한다.DP[i][j] = (i, j)에서 도착지 (M - 1, N - 1)까지 이동하는 경우의 수우선 입력을 받자.모든 지점이 도착지에 도달한다는 보장이 없으므로, dp는 -1로 초기화하자.dfs를 하며 만약 도착지에 도달했다면 1을. 이미 방문한 곳이라면 dp[x][y]를 반환해주자.그게 아니라면 새로운 탐색을 시작해야 하므로 dp[x][y..

문제https://www.acmicpc.net/problem/6593풀이L, R, C로 이루어진 직육면체에서 상하좌우, 위, 아래로만 이동하며 출발지 S에서 도착지 E로 도착하는데 걸리는 최단 시간을 구하는 문제다.BFS를 3차원으로 확장하면 되는 기본 문제다.우선 시작 전 문자나 상태를 정의해주자.상위 그래프 문제로 갈수록 이처럼 문제에서 주어지는 문자들을 자신의 언어로 변환해주는게 실수를 방지하는데 도움이 된다.L, R, C가 모두 0이 아닐 때 까지 입력을 받으며 탐색을 진행하면 된다.그래프 정보를 입력받으며 벽을 표시해주고, 시작점과 종료점의 위치를 파악해주자.(sl, sr, sc, el, er, ec)각 층마다 한 줄 공백 입력이 주어진다는 점에 유의하자.기본 BFS를 3차원으로 확장해 구현해주..

문제https://www.acmicpc.net/problem/2583풀이K개의 직사각형을 제외한 나머지 영역의 개수와 넓이를 구하는 문제다.우선 문제의 예제를 살펴보자.K개의 직사각형에 대해 표시하면 다음과 같다. 왼쪽아래 좌표와 오른쪽위 좌표가 주어지는데 그림을 회전시켜보자.일반적인 배열의 논리적 표현과 같다.그러면 사각형의 넓이는 어떻게 구할까?전체적으로 행과 열을 축소시키면 된다.즉, 이 문제에서 다룰 범위는 M, N에 대해 (0, 0) ~ (N - 1, M - 1)가 된다.K개의 좌표를 입력받아 블럭표시를 해주자.이제 블럭( BLCOK )이 아니고, 방문한적 없는( EMPTY )영역들에 대해 BFS를 진행하면된다.bfs(i, j)는(i, j)에서 bfs를 하고, 하나로 연결된 영역의 넓이를 반환한..

문제https://www.acmicpc.net/problem/17071풀이수빈이와 동생이 각각 N, K에서 이동할 때 몇 초 후에 서로 만날 수 있는지 계산하는 문제다.수빈이는 다음과 같이 움직일 수 있다.X - 1X + 12X동생은 다음과 같이 움직일 수 있다.N + KK는 경과 시간이자. 동생이 움직일 수 있는 거리를 의미한다. 풀이에서는 step으로 표현하겠다.만약 N == K인 경우 수빈이와 동생은 제자리에서 만나므로 탐색이 불필요하다. 걸린 시간은 0초다.bfs로 N부터 탐색을 시작하자.큐가 비어있거나, k(동생의 이동 위치)가 500,000이하라면 탐색을 계속해야 하므로 동생의 이동거리부터 계산하며 조건식에 포함시켜주자.본격적으로 풀이를 하기전에 시간복잡도에 대해 생각해보자.수빈이는 X - 1..

문제https://www.acmicpc.net/problem/28288풀이가로, 세로가 5 * N으로 이루어진 일정을 참고해, 각 열에 존재하는 'Y'의 비율 가장 많은 요일을 출력하는 문제다.만약, 각 일정이 가지는 Y의 수가 동일한 경우 ','를 구분자로 같이 출력해주면 된다.우선, 문자열 결합을 쉽게 하기 위해 StringJoiner를 사용했다.이후 입력받은 char 배열에 대해 각 열에 존재하는 Y의 개수를 cnt 배열에 기록해주자.동시에 최대 개수를 따로 기록해주자.이제 cnt 배열에서 기록한 최대 개수와 동일한 개수의 Y가 존재하는 일정을 구분자와 결합해 출력하면 된다.소스코드보기

문제https://www.acmicpc.net/problem/2482풀이바텀업보다 탑다운 방식으로 접근하면 쉬워지는 문제다. 원형을 이루는 N개의 색상환 표에 대해 인접하지 않은 색을 K개 선택하는 경우의 수를 구해야 한다.경우의 수가 너무 커지지 않게 1e9 + 3으로 나눈 나머지를 출력해야 한다. dp[N][K] : N개의 색상에 대해 인접하지 않는 K개의 색을 선택하는 경우의 수문제를 단순화해보자. 다음이 성립한다.dp[N][1] = Nif K > N / 2, dp[N][K] = 0문제에서 주어진 그림을 예시로 설명하겠다.우선 빨강색(N번째)을 선택해보자.N번째 색을 선택할 때, 인접한 N - 1번(다홍색)은 선택할 수 없다. N - 2번(주황)을 선택해야하고, 이 때 K - 1개의 색을 선택하면 ..