본문 바로가기

전체 글145

2Xn 타일링 #11726 c++ 풀이 https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net n=1 일때 경우의 수 1 n=2 일때 경우의 수 2 n=3 일때 경우의 수 3 n=4 일때 경우의 수 5 여기서 피보나치같은 느낌이어서 그렇게 풀었다. #include using namespace std; int n; int dp[10001]; int main() { cin >> n; dp[0] = 0; dp[1] = 1; dp[2] = 2; for (int i = 3; i 2023. 11. 10.
BABBA #9625 c++ 풀이 https://www.acmicpc.net/problem/9625 9625번: BABBA 상근이는 길을 걷다가 신기한 기계를 발견했다. 기계는 매우 매우 큰 화면과 버튼 하나로 이루어져 있다. 기계를 발견했을 때, 화면에는 A만 표시되어져 있었다. 버튼을 누르니 글자가 B로 변했 www.acmicpc.net 차분히 먼저 적어보았다. dp문제는 규칙을 찾는게 중요하다. iter수 -> 모양 A개수 B개수를 써봤다. 0-> A 1 0 1-> B 0 1 2-> BA 1 1 3-> BAB 1 2 4-> BABBA 2 3 여기서 점화식이 보였다. 5-> BABBABAB 3 5 6-> BABBABABBABBA 5 8 그결과 dp[i][1] = dp[i - 1][0] + dp[i - 1][1]; dp[i][0] = .. 2023. 11. 10.
스티커 #9465 c++ 풀이 https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 틀린 코드 : #include #include using namespace std; int T; int n; int s[2][100001]; int dp[2][100001]; int main() { cin >> T; while (T--) { memset(dp, 0, sizeof(dp)); memset(s, 0, sizeof(s)); cin >> n; for (int i = 0; i < .. 2023. 11. 8.
RGB거리 #1149 c++ 풀이 https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 집을 색칠할건데, 비용이 가장 작은 경우를 출력하라는 dp문제이다. 경우의 수는 다음과 같다. 이번에 R을 칠할 것이면, 다음에는 GB중 하나를 선택해야한다. 이번에 G을 칠할 것이면, 다음에는 RB중 하나를 선택해야한다. 이번에 B을 칠할 것이면, 다음에는 RG중 하나를 선택해야한다. 3가지 경우의 cost를 전부 세야하는구나를 알았다. 따라서 RGB로 시작하는 각각의 비용.. 2023. 11. 6.

티스토리툴바