🔗문제 보러가기 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 🧑🏻‍💻풀이 과정 피보나치 함수를 호출했을 때, \( n = 0 \) 또는 \( n = 1 \)일 때의 0과 1의 출력 개수를 세야 합니다. (즉, 위 문제에서 주어진 소스 코드에서 if(n == 0)과 if (n==1)에 해당할 경우) 1. Top-down 방식으로 DP 배열을 통해 중복 계산 최소화 방법 시도 (실패) 피보나치 함수를 재귀로 구현했을 때의 문제점이 바로 중복 계산입니다. 중복 계산이 이루어지기에 시간이 터무니없이 많이 걸리는 것이고, 이것을 개선하기 위해 DP 배열을 사용하여 이미 계산된 N이라면 계산하지 않는 것이죠. 하..

🔗문제 보러가기 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 🧑🏻‍💻풀이 과정 \( n = 1\)부터 하나씩 그려보면, 피보나치 수열의 규칙이 생깁니다. \( n = 1\)과 \( n = 2\)를 베이스로 삼아, \( n = 3\)부터는 \( n - 2\)와 \( n - 1\)을 가지고 조합해 나가는 방식이다 보니, 피보나치 수열과 같은 규칙이 생기는 것 같네요. ✏️ 소스 코드 및 결과 #include #include using namespace std; void SetFastIO() { ios::sync_with_stdio(..

🔗문제 보러가기 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 설명 N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N이 주어진다. (1 ≤ N < 15) 출력 첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다. 예제 입출력 풀이 전략 \( N \times N\) 체스판에서 퀸이 서로 공격을 하지 못하게 놓는 경우의 수를 구하는 문제입니다. 퀸은 자신이 놓인..

🔗문제 보러가기 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 문제 설명 지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M×N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 8×8 크기의 체스판으로 만들려고 한다. 체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이..

🔗문제 보러가기 문제 설명 두 정수 A와 B를 입력받은 다음, A+B를 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 A와 B가 주어진다. (0 < A,B < 1010000) 출력 첫째 줄에 A+B를 출력한다. 예제 입출력 풀이 전략 입력 범위가 보시다시피, 말도 안 되게 큰 숫자입니다. Java는 BigInteger 클래스가, Python은 심지어 그냥 해도 되는데, C++은 왜 안 돼요...? unsigned long long 자료형으로도 커버할 수 없다고 판단하여, 문자열(string)로 처리하여 풀어야겠다 생각했습니다. 주의해야 할 사항은 다음과 같습니다. 두 수의 가장 뒷자리부터 서로 더하되, carry 처리를 잘해줘야 한다. (매우 중요) 두 수의 자릿수가 서로 다를 경우, 더 긴 수의 앞 ..

🔗문제 보러가기 2869번: 달팽이는 올라가고 싶다 첫째 줄에 세 정수 A, B, V가 공백으로 구분되어서 주어진다. (1 ≤ B < A ≤ V ≤ 1,000,000,000) www.acmicpc.net 문제 설명 땅 위에 달팽이가 있다. 이 달팽이는 높이가 V미터인 나무 막대를 올라갈 것이다. 달팽이는 낮에 A미터 올라갈 수 있다. 하지만, 밤에 잠을 자는 동안 B미터 미끄러진다. 또, 정상에 올라간 후에는 미끄러지지 않는다. 달팽이가 나무 막대를 모두 올라가려면, 며칠이 걸리는지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 세 정수 A, B, V가 공백으로 구분되어서 주어진다. (1 ≤ B topHeight; unsigned int days = 1; // 소수점도 계산하기 위해 한 쪽을 실수형으로 ..