jmmm_25

1182번 부분집합의 합 문제는 입력으로 주어진 원소들의 부분집합들 중에서 합이 S가 되는 부분집합의 갯수를 찾으면 된다. 알고리즘은 간단하나, 부분집합을 구하는 방법을 알지 못하면 어려운 문제가 될 수 있다. 어려운 문제는 아닌데, 전역변수와 파라미터의 변수명을 같게하여 계속 틀렸다고 나온 문제라 주의해야할 것 같다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445#include using namespace std; int N, S, ret, abs_s;int number[21];int flag[21]; void powerset(int n, int depth) { if (n == depth) { int s..

1234567891011121314151617181920212223242526272829#include int data[]={1,2,3,4};int flag[]={0,0,0,0}; void powerset(int n,int depth){ if(n==depth){ int i; printf("{"); for(i=0;i

1018번 체스판 다시 칠하기 문제는 나의 경우에는 완벽한 체스판을 2개를 만들어 놓고 시작하였다. 왼쪽 위의 색상이 White인 경우와 Black인 경우인 2가지가 있다. 이 white_chess와 input을 통해 만들어 놓은 map 배열의 같은 자리들을 비교하여다를 경우에 result 값을 +1 하는 식으로 알고리즘을 풀이했다. 이 문제는 white 체스판과 black 체스판 둘 다 결과를 구해서 최소값을 찾는 것이 중요하다. 소스는 아래와 같다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273 #inc..

유레카이론은 1부터 45까지 3중 for문을 이용한 완전탐색으로 해결할 수 있다.input이 1000까지이므로, 삼각수를 계산할 때 n(n+1)/2 > 1000이 되는 n을 찾으면 된다.따라서 n은 45가 된다. 그 후, 3중 for문을 이용하여 삼각수를 3개를 모두 다 더하여, input 값인 k와 같으면return 1 을 해주고, k와 같은 값을 찾을 수 없으면, return 0 을 반환해주면 된다. 소스는 아래와 같다. 1234567891011121314151617181920212223242526272829303132333435363738#include #define MAX_N 46using namespace std; int samgaksu[MAX_N]; int sol(int k) { for (in..

2231번 분해합 문제도 완전 탐색 알고리즘으로 해결할 수 있다.우선 분해합에 대해서 이해를 해야한다. 위의 문제 설명처럼 245의 분해합은 245 + 2 + 4 + 5 인 256이 된다.따라서, 245는 256의 생성자가 된다. for문을 이용하여 N이 1 부터 1000000까지 돌려보면 된다.백만이면, 시간 복잡도는 1초도 안걸릴 것이다. 1부터 숫자를 증가시켜가며, 198일 때 198 + 1 + 9 + 8 인 216이 input의 216과 같다면 break를 걸어 종료를 하고 출력시킨다.만약 생성자를 찾을 수 없다면, 0을 출력하면 된다. 여기서 중요한 것은 198의 각 자리 수를 어떻게 더하느냐이다. '%' 연산자를 이용하여 간단하게 처리할 수 있다. number가 198이라고 가정하면, 198 ..

3085번 사탕게임 문제는 완전 탐색 알고리즘으로 해결하면 된다.map이라는 char 배열에 input을 저장시킨다. 문제는 완전 탐색이기에 배열의 처음부터 끝까지 다 훑어보면 된다. 힌트의 예처럼 4번 행의 Y와 C를 바꾸면 사탕 4개를 먹을 수 있다. YCPZY YCPZYCYZZP CYZZPCCPPP -> CCPPPYCYZC CYYZCCPPZZ CPPZZ 즉, 파란색으로 쓰여진 C 사탕 4개를 먹을 수 있는 것이다.내 소스에서는 우측과 아래로만 위치를 바꿀 수 있게 하였다. 처음 sol(0,0) 함수를 호출하면 (0,0)과 (0,1)을 교체한 후, 이중 for문을 통해 최대로 먹을 수 있는 사탕의 개수를 세고 이 과정이 완료되면(0,0)과 (1,0)을 교체한 후, 같은 방식을 수행하였다. 또한, 사탕..

2309번 일곱난쟁이 문제는 완전 탐색 알고리즘으로 문제를 해결하면 된다.Brute Force 알고리즘을 공부하던 중에 추천 문제로 '일곱 난쟁이' 문제가 있길래 풀어봤다. 나 같은 경우에는 9명의 난쟁이의 키를 모두 다 더한 후, 2명의 난쟁이의 키를 빼는 식으로문제를 해결하였다.그 후, 문제에서 요구하는 것처럼 일곱 난쟁이의 키를 오름 차순으로 정렬 후 출력하였다. 소스는 아래와 같다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253 #include #include #include #include #define PEOPLE 9#define FINDVALUE 100using n..