![]()
풀이#include #define MAX 1000001 #define MOD 1000000009 int n; long long d[MAX]; using namespace std; int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int T; cin >> T; d[1] = 1, d[2] = 2, d[3] = 4; while(T--) { cin >> n; for( int j = 4; j d[j] = (d[j - 3] + d[j - 2] + d[j - 1]) % MOD; } cout } ..
문제 링크https://www.acmicpc.net/problem/2561문제 난이도다이아몬드 5문제 설명주어진 순열을 정렬된 상태로 만들기 위해서 3번 이하의 교환으로 가능한지를 판별하는 문제입니다. 교환은 연속된 수열을 뒤집는 방식으로 이루어집니다. 주어진 순열을 가능한 한 적은 횟수로 정렬된 상태로 만들어야 합니다.문제 풀이아이디어이 문제를 해결하기 위해 다음과 같은 접근 방식을 사용합니다:비정상 구간 확인: 순열에서 연속된 숫자 간의 차이가 1보다 큰 부분과 단조증가 또는 단조감소가 아닌 부분을 확인합니다.비정상 구간 뒤집기: 비정상 구간을 뒤집어서 순열을 정렬된 상태로 만드는 방법을 찾습니다.백트래킹: 백트래킹을 이용해 최대 3번의 교환으로 문제를 해결합니다해당 풀이가 가능한 이유는 실제로 비정..
![]()
https://www.acmicpc.net/problem/17951 이진탐색을 이용해서 그룹 당 문제개수의 합의 최소를 구하는 문제이진탐색을 사용해서 푸는 것이란 것을 몰르고 풀었다면, 이걸 이진탐색을 사용하겠다는 생각이 들었을까 .. 싶었던 문제였다. import java.io.*;import java.util.*;public class Main { static int arr[]; static int N; static int M; public static void main(String[] args) throws IOException { BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); ..
![]()
https://www.acmicpc.net/problem/2529 문제 풀이import sysimport itertoolsdef check(array, ptr): global n for i in range(n): if array[i] == '>' and not ptr[i] > ptr[i + 1]: return False elif array[i] == ' 모든 조합의 경우를 check라는 검증 함수를 통해 필요한 부분만 값을 받아올 수 있도록 작성했다. 역순 순열을 통해 모든 순회를 통해 검증하는 것이 아닌 Max 값과 min 값을 각각 따로 받아 값을 받아 최적화를 진행했다.
![]()
문제 https://www.acmicpc.net/problem/17127 Algorithm 구간을 총 4개를 나누어야 하므로 for문을 3개 사용하여 구간을 나누었다. 위 그림과 같이 for문으로 구간을 나누어 주었다. 최소한 그룹에는 1개의 나무가 존재해야 하므로 구간을 0~n-1로 설정하고 i는 j,k를 고려하여 0~n-3까지, j는 k를 고려하여 1자리를 남겨야 하므로 i+1부터 n-2까지, k는 j+1부터 n-1까지 설정해준다.이제 구간끼리의 곱을 구해야 한다. 우리가 설정한 i,j,k에 따라 구간은 [0,i] , [i+1,j] , [j+1,k] , [k+1,n-1]의 구간이다.여기서 누적합의 개념을 사용해서 누적합이아닌 누적곱으로 바꾸어 주었다. prefix[0] = 1로 설정하고 계속 곱하고..
