Problem Solving116 [Problem Solving] BOJ 13397 : 구간 나누기 2 문제 링크 : https://www.acmicpc.net/problem/13397 배열을 최대 M개로 분할할 수 있을 때, 각각의 분할의 최댓값-최솟값중 가장 큰 값을 구하는데, 그것의 최솟값을 구하는 문제이다. 1.배열 v가 있다.low = 0high = max(v)-min(v)로 설정한다. 2.low mid = (low + high) / 2로 설정한다. func(x)함수는 각각의 분할의 최댓값-최솟값이 x이하의 값이 되도록 분할하는 함수이다. 이 때 분할의 개수가 M보다 크면 false를 return, 그렇지 않다면 true를 반환한다.x가 작을수록 잘게 분할되어 분할이 많아지고, x가 클수록 크게 분할되어 분할의 수가 작아진다. func(mid)가 true라면분할이 M개 이하로 생긴 것이다.ans.. 2025. 2. 22. [Problem Solving] BOJ 5582 : 공통 부분 문자열 문제 링크 : https://www.acmicpc.net/problem/5582 가장 긴 공통 부분 문자열의 길이를 구하는 문제이다.dp[i][j]는 s[j - 1]와 t[j - 1]이 같을 때, s[:i]와 t[:j]의 가장 긴 공통 부분 문자열의 길이가 된다.따라서 s[j - 1] == t[j - 1]일 때, dp[i][j]를 dp[i - 1][j - 1] + 1로 설정한다.dp테이블을 다 채우고, 테이블 내 가장 큰 값이 답이 된다. import sysread = sys.stdin.readlines = read().rstrip()t = read().rstrip()answer = 0dp = [[0] * (len(s) + 1) for _ in range(len(t) + 1)]for i in range.. 2025. 2. 21. [Problem Solving] BOJ 1783 : 병든 나이트 문제 링크 : https://www.acmicpc.net/problem/1783 병든 나이트가 거쳐갈 수 있는 칸의 최대 개수를 구하는 문제이다. 거쳐간 칸의 최대 개수가 5개 이상인 경우에는 4가지 움직임을 각각 1회 이상 수행했어야하고, 5개 미만인 경우에는 그렇지 않았어도 된다. 아래로 2칸 이상, 오른쪽으로 6칸 이상 이동할 수 있다면 4가지 기본 움직임을 모두 선제적으로 1회씩 수행하고, 오른쪽으로 1칸씩 이동하는 것을 적절히 수행 하여 거쳐간 칸의 최대 수를 구할 수 있다. 이 점을 이용해서 모든 경우를 직접 손으로 그려보며 if문을 직접 코딩하여 풀면 된다. #include #include #include #include #include #include #include #include #.. 2025. 2. 20. [Problem Solving] BOJ 2623 : 음악 프로그램 문제 링크 : https://www.acmicpc.net/problem/2623 노드의 수와 순서의 수가 N과 M으로 주어진다.N이 6이고, M이 3일 때, M개의 순서가1 4 36 2 5 42 3으로 주어진다면이는1 -> 4, 1 -> 3, 4 ->36 -> 2, 6 -> 5, 6 -> 4, 2 -> 5, 2 -> 4, 5 -> 42 -> 3으로 그래프로 표현할 수 있다.이를 위상정렬 한 결과를 출력하면 된다.위상정렬을 수행했는데 그 결과가 N과 같지 않다면 위상정렬 불가능한 그래프이기 때문에 0을 출력하면 된다. import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.. 2025. 2. 19. [Problem Solving] BOJ 9084 : 동전 문제 링크 : https://www.acmicpc.net/problem/9084 Coins에 N개의 동전의 종류가 오름차순으로 있을 때, M원을 만들 수 있는 모든 경우의 수를 구하는 문제이다. DP테이블을 정의하자면 DP[M]은 M원을 만들 수 있는 모든 경우의 수이다. 일단 DP[0...M]을 0으로 초기화 하자. DP[0]의 경우, 어떤 동전도 사용하지 않는 단 한 가지의 경우로 0원을 만들 수 있으니, DP[0] = 1이다. 0번째 동전을 사용하면,0번째 동전은 Coins[0]원을 만들 수 있다.DP[Coins[0]]는 Coins[0]원을 만드는 경우의 수인데, 이것은 0원을 만드는 경우의 수(DP[0])에 Coins[0] 동전을 사용하여 Coins[0]원을 만드는 것이므로, DP[0]과 같다.D.. 2025. 2. 19. [Problem Solving] BOJ 14719 : 빗물 문제 링크 : https://www.acmicpc.net/problem/14719 2차원 세계의 단면이 있을 때, 고이는 빗물의 총량을 구하는 문제이다.loop로 밑의 행부터 위의 행으로 빗물을 채운다. 행에서 맨 왼쪽이나 맨 오른쪽에 블럭이 없어서 빗물이 고일 수 없다면 인접한 빗물을 모두 없앤다. loop가 끝나면 빗물을 모두 count해서 answer를 출력한다. #include #include #include #include #include #include #include #include #include #include #define endl '\n'using namespace std;int answer = 0;int H, W;int blocks[501][501];void input(){ c.. 2025. 2. 17. 이전 1 2 3 4 5 6 7 8 ··· 20 다음