N

문제 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다. 예를 들어 와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다. 계단 오르는 데는 다음과 같은 규칙이 있다. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다. 마지막 도착 계단은 반드시 밟아야 한다. 따라서 첫 번째 계단을 ..

#include #include using namespace std; int solution(int m, int n, vector puddles) { int answer = 0; int check[101][101] = {0, }; int visited[101][101] = {0, }; for(int i = 0; i < puddles.size(); i++) check[puddles[i][1]][puddles[i][0]] = -1; visited[1][0] = 1; for(int i = 1; i

문제를 잘 읽다보면 타일의 한 변의 길이가 피보나치와 같이 증가하는 것을 알 수 있다. 그래서 피보나치를 이용하여 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