본문 바로가기

Programming

[백준] 10844번 쉬운 계단 수 C/C++ 풀이 출처: https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 우선 이 문제를 해결하는데 많은 시간이 걸렸다. 이 계단수는 특별한 규칙을 갖고있다. 한번 찾아보도록 하자. 45676(O) 890(X) 709(X) $$(n=자릿수, \quad C=계단\:수)$$ \(n=1\)일 경우, 다음과 같다. \(C=9\) 1, 2, 3, 4, 5, 6, 7, 8, 9 \(n=2\)일 경우, 다음과 같다. \(C=17\) 10, 12 21, 23 32, 34 43, 45, 54, 56 65, 67 76, 78 87, 89 98 \(n=3\)일 경우, 다음과 같다. \(C=.. 더보기
[백준] 1011번 Fly me to the Alpha Centauri C/C++ 풀이 출처: https://www.acmicpc.net/problem/1011 1011번: Fly me to the Alpha Centauri 우현이는 어린 시절, 지구 외의 다른 행성에서도 인류들이 살아갈 수 있는 미래가 오리라 믿었다. 그리고 그가 지구라는 세상에 발을 내려 놓은 지 23년이 지난 지금, 세계 최연소 ASNA 우주 비행사가 되어 새로운 세계에 발을 내려 놓는 영광의 순간을 기다리고 있다. 그가 탑승하게 될 우주선은 Alpha Centauri라는 새로운 인류의 보금자리를 개척하기 위한 대규모 생활 유지 시스템을 탑재하고 있기 때문에, 그 크기와 질량이 엄청난 이유로 최신기술력을 www.acmicpc.net 풀이 공간 이동 장치 작동 횟수 규칙을 찾아보자. $$y-x=거리,\quad C=장치\.. 더보기
[백준] 2775번 부녀회장이 될테야 C/C++ 풀이 출처: https://www.acmicpc.net/problem/2775 2775번: 부녀회장이 될테야 첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 정수 k, 두 번째 줄에 정수 n이 주어진다. (1 더보기
[백준] 2869번 달팽이는 올라가고 싶다 C/C++ 풀이 출처: https://www.acmicpc.net/problem/2869 풀이 먼저 달팽이가 올라가는 규칙을 찾아보도록 하자. 먼저 달팽이가 하루에 올라갈 수 있는 거리는 \(A-B\) 이다. 하지만, \(A-B\) 라고 생각해 \(N\)값을 계산하는건 큰 오류이다. 달팽이는 나무 막대를 모두 올라가면, 밤에는 미끄러지지 않는다. 즉, 달팽이가 미끄러지는 최대 지점을 찾아야한다. 최대 지점은 \(V-A\) 라고 계산할 수 있다. 달팽이가 나무 막대를 전부 올라가는데 걸리는 일수가 \(S\)이고, 최대 지점을 \(L\)이라고 가정하면 식은 다음과 같다. $ N=\frac{L}{A-B}+1 $ 하지만 이 수식에는 함정이 있다. 다음 예시를 보도록 하자. $ N=\frac{3}{4-2}+1 $ 이 수식대로라면.. 더보기
[백준] 1193번 분수 찾기 C/C++ 풀이 출처: https://www.acmicpc.net/problem/1193 1193번: 분수찾기 첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다. www.acmicpc.net 풀이 먼저 모든 양의 유리수의 집합은 셀 수 있는 무한집합이다. 양의 유리수의 수열은 다음과 같이 나타낼 수 있다. $$ r_{1},r_{2},...,r_{n} $$ 또한, 다음 유리수들은 n/d의 형식으로 되어있고 다음과 같은 규칙을 찾을 수 있다. $$ n+d=2, \: n+d=3, \: n+d=4 \:\: ... \:\: n+d=cnt $$ 첫번째 for문에는 cnt의 값을 찾는 코드를 작성한다. 두번째 for문에서는 \(cnt\:\, mod\:\, 2 \) 의 값에 따른 분자와 분모의 값을 구하는 코드를 작성한다... 더보기
[백준] 2292번 벌집 C/C++ 풀이 출처: https://www.acmicpc.net/problem/2292 풀이 먼저 벌집의 규칙을 찾아보도록 하자. > n = 벌집의 개수 f(n) = 지나야 하는 방의 개수 if) n = 1 if) n = 6 f(n) = 1 f(n) = 2 if) n = 12 if) n = 18 f(n) = 3 f(n) = 4 벌집이 6개씩 추가로 늘어날 때마다 지나야 하는 방의 개수도 1개씩 늘어난다. $$ (단, \,n>1) $$ C/C++ 풀이 더보기
[백준] 2193번 이친수 C/C++ 풀이 출처: https://www.acmicpc.net/problem/2193 풀이 먼저 이친수를 계산하기 위한 경우의 수를 계산해보자. > n = 이친수의 자리수 f(n) = 자리수에 따른 이친수의 개수 if) n = 1 -> f(n) = 1 if) n = 2 -> f(n) = 1 1 10 if) n = 3 -> f(n) = 2 if) n = 4 -> f(n) = 3 101 1010 100 1000 1001 점화 관계 추론 1, 1, 2, 3... 식으로 수열이 늘어나고 있다. 이는 피보나치 수열의 관계와 같은 형식이라고 추측할 수 있다. $$ f_{n} = f_{n-2} + f_{n-1} \: (단,\, f_{1} = 1, f_{2} = 1) $$ C/C++ 풀이 더보기

티스토리툴바