알고리즘/수학(3)
-
백준 11947번: 이런 반전이 (C++)
https://www.acmicpc.net/problem/11947 11947번: 이런 반전이 첫째 줄에는 테스트 케이스의 개수를 나타내는 하나의 자연수 T가 주어집니다. 다음 T개의 각 줄에는 하나의 양의 정수 N이 주어집니다. (1 ≤ N ≤ 1,000,000,000) www.acmicpc.net 풀이 처음에 문자열로 1부터 하나씩 계산해보려다가 n이 최대 10억이라서 시간초과가 난다고 생각이 들었다. 그래서 고등학교때 배웠던 함수의 최댓값을 활용했다. 우선, 정수 n을 4자리 수 abcd의 형태로 나타내고 식을 세워보았다. 이렇게 n과 F(n) 을 곱한다고 가정했을 때, 초항이 큰 수가 최댓값이 된다는 것을 알았고 a에 대한 2차원 함수를 그려보니 a가 4.5일 때, 최댓값이 된다. a는 정수이기 ..
2023.01.20 -
백준 2502번: 떡 먹는 호랑이 (C++)
https://www.acmicpc.net/problem/2502 2502번: 떡 먹는 호랑이 첫줄에 첫 날에 준 떡의 개수 A를 출력하고 그 다음 둘째 줄에는 둘째 날에 준 떡의 개수 B를 출력한다. 이 문제에서 주어진 D, K에 대해서는 항상 정수 A, B (1≤ A ≤ B)가 존재한다. www.acmicpc.net 풀이 피보나치의 첫번째 항과 두번째 항을 구하는 문제. 먼저, 첫번째 항과 두번째 항만 구하면 되기 때문에 변수를 최대한 줄여 나타냈다. 그리고 첫번째 항과 두번째 항의 상수의 점화식을 도출해서 X[31][2]를 선언, 2차원 배열에 순서대로 저장해주었다. (여기서는 2번째부터 표현했는데 다시보니 첫번째부터 구해도 됐다.) (X1 제일 앞에 1, X2 제일 앞에 0) 변수가 두개가 되기 ..
2023.01.18 -
백준 1111번: IQ Test (C++)
https://www.acmicpc.net/problem/1111 1111번: IQ Test 다음 수를 출력한다. 만약 다음 수가 여러 개일 경우에는 A를 출력하고, 다음 수를 구할 수 없는 경우에는 B를 출력한다. www.acmicpc.net 풀이 풀어보려고 시도했으나 접근법을 몰라 풀이 방법만 찾아봤다. 그리고 나름대로 다시 분석하여 풀어봤다. 케이스를 나누어서 구하는 방식이었는데 공식을 보니 고등학교때 풀었던 변수의 범위에 따라 케이스를 나누어서 계산하는 문제가 생각났다. 우선 차례대로 식을 쓰면 이런 느낌이다. 그리고 여기서 첫번째 식과 두번째 식을 연립해서 a와 b에 대한 식으로 나타내면 이런식으로 나타낼 수 있다. 이제 N과 X항에 따라 각 케이스를 구할 수 있다. N = 1 , 먼저 X1 밖..
2023.01.18