Be a developer

주어지는 숫자의 순서가 바뀌지 않기 때문에 연산자만 순열을 통해 풀면된다. 수의 개수가 최대 11개이므로 연산자의 개수는 최대 10개가 되어 순열로 풀 수 있는 문제이다. 브루트포스로 모든 경우의 수를 만들어 보면서 최댓값과 최솟값을 구한다. algorithm 헤더의 minmax_element함수를 이용한다. 자세한 설명은 코드의 주석으로.. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950#include #include #include using namespace std; int main(int argc, char** argv) { int n; cin >> n; vector v(n); ve..

이 문제는 배열 안에 중복된 수가 있어도 next_permutation이 잘 작동한다는 것을 이용해서 푼다. 예시와 같이 k=8, s={1,2,3,5,8,13,21,34}인 경우 0을 먼저 6개 넣고, 다음에 1을 2개 넣어야 한다. 그렇게 되면 0 0 0 0 0 0 1 1과 같은 vector가 만들어지고, 이를 next_permutation을 사용해 섞으면 뒤에서 부터 섞이게 되어 모든 순열을 다 검사할 수 있다. 만약 1을 6개 먼저 넣고 0을 2개 넣게 되면, 1 1 1 1 1 1 0 0 과 같은 vector가 만들어지고, 모든 순열을 다 검사하지 못하게 된다. 원소는 오름차순으로 입력받기 때문에 sorting할 필요가 없다. 0과 1을 vector에 넣을 때 조심해야 한다. vector v(n)과..

N이 최대 10일 때 10개의 도시 목록을 배열에 넣고 next_permutation을 통해서 풀면된다. 원소가 10개 이하이기 때문에 브루트 포스로 풀 수 있는 문제다. 한 번 갔던 도시로는 다시 갈 수 없기 때문에 순열로 풀 수 있는 문제다. 시작점은 중요하지 않다. 만약 4개의 도시가 있다면 1 -> 2 -> 3 -> 4 -> 1 이 루트와 2 -> 3 -> 4 -> 1 -> 2 이 루트에 필요한 비용은 같기 때문이다. 따라서 시작점을 정해놓고 알고리즘 풀이를 하기 때문에 시간 복잡도가 O(N * N!)보다 작다.(O( (N-1) * (N-1)!)) 처음에 순서대로 도시 번호를 넣어준 다음 순열을 돌리면서 모든 경로의 수를 구한다. 자세한 설명은 주석으로.. 1234567891011121314151..

계속 추가될 예정. 1. scanf를 잘 써보자. scanf("%1d",&num); //101010이 입력으로 들어올 때 하나씩 int형으로 읽을 수 있다. scanf("%d,%d",&num1, &num2); //10,10과 같이 정해진 형식으로 입력을 받을 수 있다. 2. 배열을 전역변수로 선언하면 모든 원소가 0으로 초기화 된다. 지역변수로 선언하면 dp[1001][10] = {}; 이렇게 초기화 해줘야 모든 원소가 0으로 초기화된다. 3. min, max return하는 함수 사용법 auto res = minmax_element(vector.begin(), vector.end()) /* *res.first => min *res.second => max */ res = max_element(vecto..

abs함수와 max함수를 쓴다는 것 외에는 딱히 설명할게 없다. 한 가지 중요한 점은 순열을 사용하기 위해서는 먼저 정렬을 해야 한다는 것이다.(모든 경우를 다 돌려보기 위해서) next_permutation을 사용할 때는 첫 번째 순열을 돌린 후에 해야 하기 때문에 do-while을 사용하자. 시간복잡도는 N이 최대 8이므로 8!로 순열로 해결할 수 있는 문제임을 알 수 있다. 1234567891011121314151617181920212223#include #include using namespace std; int main(int argc, char* argv[]) { int n, ans = 0, sum; cin >> n; int *bf = new int[n]; for (int i = 0; i > ..

순열은 순서가 부여된 임의의 집합을 다른 순서로 뒤섞는 연산이다. 다음 순서의 순열을 찾으려면 c++에서는 next_permutation과 prev_permutation이 존재하기 때문에 사용하면 된다. 직접 구현하기 위한 방법은 아래와 같다. 1. A[i-1] =i 이면서 A[j] > A[i-1] 를 만족하는 가장 큰 j를 찾는다.(다음 순열은 순열을 하나의 수로 봤을 때 더 큰 수가 되어야 하므로, A[i-1]보다 큰 수를 앞으로 가져와야 한다. 작은 수를 앞으로 가져오는 것은 작은 수로 바꾸는 것이기 때문이다.) 3. A[i-1]과 A[j]를 swap한다. 4. A..

모든 방법의 수를 구하는 것이기 때문에 브루트포스로 푼다. 1,2,3 3가지 경우가 10번 가능하기 때문에 최대 3^10의 시간복잡도이다. 하지만 1을 10자리로 했을 때 최대의 경우의 수가 생기므로 3^10보다는 작을 것이다. 3^10도 1초의 제한시간 안에 가능하다. for문으로 풀려면 10개의 for문을 작성해야한다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162#include int main() { int t; scanf("%d",&t); while (t--) { int ans = 0; int n; scanf("%d",&n); for (i..

어렵다곳 생각하지말고 문제부터 천천히 읽는다.대충 읽다가 폴리오미노, 테트로미노가 뭔지 제대로 모르고 풀고 있었다.테트로미노는 위 사진에서 나오는 각각의 도형이다. 그리고 문제에서 구해야 하는 것을 제대로 읽지 않았는데, 테트로미노 5종류 중 하나를 놓았을 때 최대값을 구하는 것이다.(대칭 및 돌려서 나오는 모양도 포함 총 19가지) 다음으로 시간제한을 본다.도형을 돌려서 만들 수 있는 모든 경우의 수는 19가지이다. 그리고 N*M 안에 넣어야 하므로 19 * 500^2이 경우의 수의 최대값이다.천만을 넘지 않으므로 브루트포스로 풀 수 있다.모든 경우의 수를 어떻게 돌려보아야 할까? 테트로미노의 한 블럭을 기준으로 해서 모든 경우의 수를 돌려본다.코드가 복잡해지므로, 3차원 배열을 이용해서 테트로미노의 ..