[ 문제 ] [ 구현 ] 성냥개비의 개수가 주어졌을 때 만들 수 있는 가장 작은 수는 DP를 통해 구했고(그리디로 가능하지만 0과 6사이의 예외처리가 머리 아플것 같음) 가장 큰 수는 그리디로 풀었다. int d[10] = { 2,5,5,4,5,6,3,7,6,6 }는 우선 각각의 숫자를 만들어내는 성냥개비의 개수를 저장한 것이다. 이를 기반으로 가장 큰 수를 먼저 생각해보면 가장 큰 수는 최대한 많은 숫자를 통해 구성해서 자릿수를 늘리는게 좋으므로 가장 적은 성냥개비를 통해 만들 수 있는 숫자인 1을 계속해서 붙이는 식으로 구성될 것이다. '1'이라는 숫자는 성냥개비가 2개 필요하므로 성냥개비의 숫자가 홀수일 경우 성냥개비가 3개 필요한 숫자인 '7'을 추가적으로 맨 앞에 활용해주면 된다. 이때 주의할 ..
[ 문제 ] [ 구현 ] 누적합 문제인데 그냥 누적합 문제가 아니라 나머지를 활용해야 한다. 여기서 핵심 아이디어는 나머지 연산을 활용하여 m으로 나눈 나머지를 누적합으로 구해놓고 i번째 인덱스와 j번째 인덱스가 같으면 i+1 ~ j까지의 합이 m으로 나눠떨어진다는 것이다. 예시를 들면 n=5, m=3 1 2 3 1 2로 입력이 주어졌을 때, 누적합 배열은 해당 인덱스번째까지의 누적합을 3으로 나눈 값을 저장 1 0 0 1 0 하지만 이 상태로 그냥 연산을 돌리면 시간초과의 우려도 있을 뿐더러(n^2, n> n >> m; int tmp; for (int i = 1; i > tmp; dp[i] = (dp[i-1] + tmp) % m; arr[dp[i]]++; } for (int i = 0; i < m; i..
[ 문제 ] [ 구현 ] 전형적인 브루트포스 문제이다. dfs를 이용하여 모든 경우의 수를 탐색하였다. 조건 중에 주어진 연산의 결과는 항상 -10억 ~ 10억이므로 각각 -1e9, 1e9로 잡고 dfs를 돌리면서 최대값, 최솟값을 갱신해주는 식으로 진행하였다. dfs(int a, int b, int c, int d, int idx, int sum)의 형식으로 파라미터를 뒀다. a,b,c,d는 각각 남은 +,-,*,/ 연산자들의 숫자를 의미한다. dfs를 돌때마다 각각 a,b,c,d가 0이상인지 체크하고, 해당 연산자를 사용하였다는 의미로 -1을 반영하여 다음 dfs 파라미터로 넘겨주었다. 해당 dfs내에서 사용할 연산자가 정해지는 순간에 arr[idx]를 더할지 뺄지 곱할지 나눌지 또한 결정되므로 su..
[ 참고 ] 전형적인 bfs문제로 3차원 bfs문제중 유명한 7569번 토마토와 별반 다르지 않다. https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net [ 문제 ] [ 구현 ] dx,dy,dz로 3차원, 동서남북상하를 이동할 수 있도록 준비해두고 queue을 이용한 bfs로 풀었다. 주의해야할 점은 주어지는 정보가 층, 행, 열의 순으로 주어지고 queue에 집어넣고, 가능한 범위를 벗어나지 않는지 검사할때도 이 규칙성을 잘..
[ 문제 ] [ 구현 ] VIP석이 없는 경우에 피보나치 수열의 형태로 경우의 수가 나타난다는 아이디어를 떠올리기 어려웠다. 이를 알고난 뒤, VIP석이 나타날 때마다 끊어서 VIP석 사이의 좌석의 개수에 해당하는 피보나치 수열을 ans에 계속 곱해나갔다. 맨 처음 부터 첫번째 VIP좌석까지, 마지막 VIP좌석으로부터 마지막 좌석(n번째)까지의 경우에도 알맞는 값을 ans에 곱해줄 수 있도록 VIP좌석을 관리하는 벡터에 따로 0과 n+1을 넣어주었다. [ 코드 ] #include #include using namespace std; int n, m; vector vip; int dp[41] = { 1,1 }; int ans = 1; int main() { cin >> n >> m; //필요한 피보나치 수..
[ 문제 ] [ 구현 ] 하나의 수를 제거하는 경우와 제거하지 않는 경우를 나누어서 생각해야 한다. 따라서 int dp[2][100001]의 2차원 배열을 선언 dp[i][j] -i=0일 때: 수를 하나도 제거하지 않은 상태로, arr[j]의 숫자를 포함시키며 만들 수 있는 연속된 수열 합의 최대값 -i=1일 때: 수를 한 가지 제거하면서, 만들 수 있는 연속된 수열의 합의 최대값(말로 딱 정의하기 애매하다) 점화식으로 확인하면 dp[0][i] = max(dp[0][i - 1] + arr[i], arr[i]) dp[1][i] = max(dp[0][i - 1], dp[1][i - 1] + arr[i]) i) dp[0][i] = max(dp[0][i - 1] + arr[i], arr[i]) 우선 dp[0][..
[ 참고 ] https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 를 먼저 풀면 좋은 문제이다. [ 문제 ] [ 구현 ] N이 1000이므로 시간복잡도 O(N^2)의 이중 for문으로 풀었다. if(arr[i] > arr[j]) dp[i] = max(dp[i], dp[j] + 1); 의 점화식을 이용해 최대 길이를 구함과 동시에 record배열을 하나 더 만들어 dp[i]..
