미소를뿌리는감자의 코딩

https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 오늘따라 집중도 안되고..ㅠ~~!! 뭔가 손에 잡히지 않지만... 그래도 책상에 앉아는 있어보려고 노력하는 중이다..ㅎ 1. 접근 방법 이번 문제는 읽으면서 작년도 알고리즘 시간에 들었던 0/1 Knapsack 이 떠올랐다. 디자인 방법 중에서는, 1) 전체 경우를 헤아려보는 방법, 2) BFS (넓이 우선 탐색) 3) DFS (깊..

https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 1. 접근 방법 이번 문제의 눈에 띄는 특징은 단연 시간과 메모리 제한이라고 할 수 있다. 시간 제한의 경우 0.25초, 메모리 제한의 경우 128MB 이었다. 즉, 재귀 함수가 대놓고 문제에 적혀져 있지만 그것은..! 함정이다! 정답 비율이 낮은 이유가 여기에 있을 것 같다. 코드가 적혀져 있다고 해당 코드를 이용하여 문제를 풀면 시간 초과로 풀지 못한다. 또한, 시간 제한이 이렇게 낮다? -> 규칙이 있을 것 같다. 라는 느낌이 들었다. 그래서 피보나치 수들을 하나씩 적어나갔고, 규칙을 찾..

https://www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 1. 접근 방법 이번 문제는 조합 문제 + 큰 수 처리 문제라고 할 수 있다. 강 서쪽의 사이트 개수를 기준으로 강 동쪽의 사이트들을 정하게 되면, 위에서 아래로부터 순서대로 강 서쪽의 사이트들과 연결지으면 되기 때문이다. 따라서 (강 동쪽의 사이트 개수)C(강 서쪽의 사이트 개수) 를 하면 된다. 이 경우, 11050번 조합 코드를 가져와서 사용하였다. 하지만, 문제가 있다면 해당 문제에서는 i..

https://www.acmicpc.net/problem/2231 2231번: 분해합 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 www.acmicpc.net 1. 접근 방법 100*x + 10*y + z + x + y + z = ? 일때, xyz를 찾아라, 이런 문제였다. 따라서 나는 101*x + 11*y + 2z 가 ? 인 xyz를 찾으면 되겠다고 생각하였다. 따라서, 1부터 값을 하나씩 증가시켜가며 xyz에 대입해나갔고, 그중에 해당하는 값이 나타날 시, 그 값을 출력하고 break 하였다. 만약 해당하는 값을 찾지 ..