jmmm_25

캠핑 문제는 그리디 알고리즘으로 해결 가능하다.답을 구하는 소스는 너무나도 간단하나, 조건 하나를 빠뜨려서 계속 틀렸던 문제이다. 조건을 잘 확인하고 푸는 습관을 가지는 것이 중요한 것 같다.나 같은 경우에는 1 < L < V < P 조건도 무시하고 문제를 풀었다.조건을 추가한 뒤에도 또 틀렸다고 나왔다.또 한 가지 문제는 V % P 의 값이 L보다 작아야한다는 것을 간과했다.이 조건을 추가한 뒤 제출하였더니 정답이었다. 문제는 단순하나 조건을 조금 더 생각해봐야 할 문제. 123456789101112131415161718192021222324252627282930#include using namespace std; int l, p, v;int main(int argc, const char * argv[..

동전 0 문제는 그리디 알고리즘을 이용하여 해결한다.입력에 (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) 이러한 조건이 있기 때문에 그리디 알고리즘이 성립한다. A1 = 1, A2는 A1의 배수, A3는 A2의 배수로 Aj의 값이 증가하기 때문이다.동전 0 문제는 어려운 문제는 아닌데, for 문의 초기값을 잘못 설정해주어, 런타임 에러가 발생하여 고생 좀 했다. 따라서, 매 순간 가장 큰 동전의 값을 이용하여 가장 큰 이익만을 찾으면 된다. 소스는 아래와 같다. 12345678910111213141516171819202122232425262728293031323334353637383940 #include using namespace std; int N,..

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..

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..