N

문제를 잘 읽다보면 타일의 한 변의 길이가 피보나치와 같이 증가하는 것을 알 수 있다. 그래서 피보나치를 이용하여 N개의 타일의 한 변의 길이를 구하였다. DP를 이용하여 arr[i] = arr[i - 1] + arr[i - 2] 의 값을 넣어주었다. 그리고 둘레의 길이를 구하는데 arr[N]의 길이와 arr[N - 1]의 길이가 필요하다는 것을 알 수 있다. arr[N] * 4와 arr[N - 1] * 2를 더하여서 answer에 넣어주고 리턴하면 끝..! 주의점은 리턴값이 long long이므로 배열도 long long으로 해줘야 한다. 만약 int형이라면 효율성 테스트에서 틀리게 된다...! #include #include using namespace std; long long solution(in..

DP를 이용하면 된다. 어떻게 풀면 될까 고민하다가 n을 1부터 차례대로 넣어봤을 때의 값을 계산해 보았다. 하다보니 피보나치와 같은 결과를 얻을 수 있어서 DP의 피보나치를 사용하였다..! #include #include using namespace std; int arr[600001] = {0, }; int solution(int n) { arr[1] = 1; arr[2] = 2; for(int i = 3; i

DP를 이용하여 문제를 풀었다..! 우선 열의 개수는 무조건 4개이다. 시간은 충분할 것 같다..! 3중 for문을 이용하도록 하자. i = 1부터 시작하여, i - 1 행의 수를 모두 비교해야 한다. 단, j != k여야 같은 열 번호의 수를 선택하지 않는다. m은 현재 행의 위치에서 이전 행의 각 열을 더했을 때 가장 큰 값을 저장하는 변수이다. 그리고 이전의 최댓값이 누적이 되므로 마지막 행에서 최댓값만 찾으면 된다..! #include #include #include using namespace std; int solution(vector land) { int answer = 0, m = 0; for(int i = 1; i < land.size(); i++) { for(int j = 0; j < ..

피보나치 수열을 DP로 풀었다. 피보나치 수열에 관한 문제는 재귀, DP, 반복문을 사용하여 풀 수 있는데, 시간을 고려해야 하는 경우는 대부분 DP를 이용하면 풀 수 있다. 배열을 이용하여 F(n) = F(n - 1) + F(n - 2) 의 값을 저장한다. 반복문을 돌면서 계속해서 F(n - 1), F(n - 2)의 값을 가져오기 때문에 재귀보다 빠르게 풀 수 있다. #include #include using namespace std; int solution(int n) { int answer = 0; int num[100001] = {0, }; num[0] = 0; num[1] = 1; for(int i = 2; i