티스토리 뷰
https://www.acmicpc.net/problem/13301
13301번: 타일 장식물
대구 달성공원에 놀러 온 지수는 최근에 새로 만든 타일 장식물을 보게 되었다. 타일 장식물은 정사각형 타일을 붙여 만든 형태였는데, 한 변이 1인 정사각형 타일부터 시작하여 마치 앵무조개
www.acmicpc.net
이번 문제는 N이 주어질 때, 주어진 조건에 따라 N개의 타일로 구성된 직사각형의 둘레를 구하는 문제이다. 처음에는 규칙을 알아내려 했지만, 잡힐듯 말듯 한 것이 너무 아리송했다. 하지만 자세히 보니 규칙이 있었다.
문제의 그림을 기준으로, 우선, N이 1일 경우는 정사각형이라 가로, 세로 길이가 각각 1이다. 그리고 N이 2일 때는 가로, 세로가 각각 1, 2이다. N이 3일 때는 가로가 3, 세로가 2이다. N이 4일 때에는 가로, 세로가 각각 3, 5이다. 하지만 직사각형이 가로가 길든 세로가 길든 답은 변하지 않으니, 편의상 가로가 더 길다고 하자. 이를 기준으로 다시 정리하자면 다음과 같다.
- N: 1 -> 1, 1
- N: 2 -> 2, 1
- N: 3 -> 3. 2
- N: 4 -> 5, 3
- N: 5 -> 8, 5
여기서 타일의 개수가 N일 때의 직사각형의 가로는 N - 1일 때의 가로 + 세로와 같으며 세로는 N - 1일 때의 가로와 같은 것을 알 수 있다. 이를 코드에 적용하면 다음과 같다.
#include <iostream>
using namespace std;
int N;
pair<long long, long long> dp[1000000]; // first: 가로, second: 세로
pair<long long, long long> Check(int num)
{
if (dp[num].first != -1)
return dp[num];
pair<long long, long long> befRec = Check(num - 1);
// 가로: 이전 직사각형의 가로 + 이전 직사각형의 세로
// 세로: 이전 직사각형의 가로
return dp[num] = { befRec.first + befRec.second, befRec.first };
}
int main()
{
ios_base::sync_with_stdio(0);
std::cout.tie(NULL);
std::cin.tie(NULL);
for (int i = 1; i <= 1000000; ++i)
dp[i] = { -1, -1 };
dp[1] = { 1, 1 };
dp[2] = { 2, 1 };
cin >> N;
pair<long long, long long> rectangle = Check(N);
// 직사각형의 둘레는 (가로 + 세로) * 2
long long answer = (rectangle.first + rectangle.second) * 2;
cout << answer << endl;
return 0;
}
'알고리즘 문제' 카테고리의 다른 글
백준 - 9095번: 1, 2, 3 더하기 (1) | 2024.02.04 |
---|---|
백준 - 1463번: 1로 만들기 (C++) (0) | 2024.02.04 |
프로그래머스 - 코딩 기초 트레이닝 캘린더 Day 4 (1) | 2024.02.04 |
백준 - 18429 근손실 (C++) (0) | 2023.09.19 |
백준 - 1189 컴백홈 (C++) (0) | 2023.09.13 |
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- 햄버거버튼
- Redux
- 넥스트js
- typescript
- 백준
- 구현
- aws
- C++
- 완전탐색
- 타입스크립트
- 프로그래머스
- 순열
- async
- 비트마스킹
- 리액트
- NextJS
- themoviedb
- SQL
- 알고리즘
- Next.js
- BFS
- 동적계획법
- 카카오맵
- 브루트포스
- react
- 다이나믹프로그래밍
- 코드스테이츠
- 자바스크립트
- 스택
- CSS
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 |
글 보관함