목록2024/01/22 (4)
미소를뿌리는감자의 코딩
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 하였다. 만약 해당하는 값을 찾지 ..
https://www.acmicpc.net/problem/2798 2798번: 블랙잭 첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다. 합이 M을 넘지 않는 카드 3장 www.acmicpc.net 1. 접근 방법 이번 문제는 brute force 알고리즘 인 만큼 하나하나 확인해나가며 풀면 되는 문제였다. 따라서, 순차적으로 숫자들을 돌아가면서, 더해주었고 기준이 되는 수보다 값이 작거나 같을 시에는 최대 힙에다가 넣어주었다. 마지막에는 최대힙의 루트를 출력하며 마무리 해주었다. 2. 코드 import java.io.IOException; import jav..