📌 문제 제목문제 링크: BOJ 11726🗒️ 문제 설명2xn 크기의 직사각형을 1x2, 2x1 타일로 채우는 방법의 수를 구하는 프로그램2xn 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력시간 제한: 1초메모리 제한: 256MB1 💡 문제 해결 아이디어테이블 정의dp[i]는 2xi 크기의 직사각형을 채우는 방법의 수점화식 찾기2xi 크기의 직사각형이 있을 때, 왼쪽 위를 2x1 크기의 직사각형으로 채우는 경우2xi 크기의 직사각형이 있을 때, 왼쪽 위를 1x2 크기의 직사각형으로 채우는 경우※ dp[i] = dp[i-1] + dp[i-2]초기값 정하기dp[1] = 1, dp[2] = 2⌛️ 시간 복잡도O(N)✅ 최종 코드import sysinput = sys.stdin.r..

📌 문제 제목문제 링크: BOJ 1149🗒️ 문제 설명RGB거리에는 N개의 집이 1번부터 순서대로 있다.집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 칠하는 비용이 주어졌을 때, 아래의 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구하여라.1번 집의 색은 2번 집의 색과 같지 않아야 한다.N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.i(2시간 제한: 0.5초메모리 제한: 128MB2 집을 칠하는 비용 💡 문제 해결 아이디어테이블 정의dp[i]는 i번째 집까지 칠할 때의 최소 비용dp[i][0]은 i번째 집이 빨강dp[i][1]은 i번째 집이 초록dp[i][2]는 i번째 집이 파랑점화식 찾기dp[1]dp[1][0] = costs[0][0]dp[1][1] = co..

📌 문제 제목문제 링크: BOJ 2579🗒️ 문제 설명계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다.각 계단에는 점수가 쓰여있고 그 계단을 밟으면 점수를 얻게 된다.다음과 같이 도착점까지 간다면 10 + 20 + 25 + 20 = 75점을 얻게 된다.계단을 오르는데는 다음과 같은 규칙이 있다.계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다.연속된 세 개의 계단을 모두 밟아서는 안된다.마지막 도착 계단은 반드시 밟아야 한다.각 계단에 쓰여있는 점수가 주어질 때, 이 게임에서 얻을 수 있는 점수의 최댓값을 구하여라.시간 제한: 1초메모리 제한: 128MB계단의 개수 계단에 쓰여있는 각 점수 💡 문제 해결 아이디어마지막 계단을 무조건 밟아야 하므로 마지막..

📌 문제 제목문제 링크: BOJ 9095🗒️ 문제 설명정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하여라.e.g. 4를 1, 2, 3으로 나타내는 방법은 총 7가지 이다.1 + 1 + 1 + 11 + 1 + 21 + 2 + 12 + 1 + 12 + 21 + 33 + 1시간 제한: 1초메모리 제한: 512MB1 💡 문제 해결 아이디어테이블 정의d[i]는 i를 1, 2, 3으로 만들 수 있는 방법의 수점화식 찾기d[4]1+1+1+1, 1+2+1, 2+1+1, 3+1 -> d[3]을 만드는 방법 + 11+1+2, 2+2 -> d[2]를 만드는 방법 + 21+3 -> d[1]을 만드는 방법 + 3※ d[4] = d[1] + d[2] + d[3]초기값 정하기d[1] = 1d[..

📌 문제 제목문제 링크: BOJ 1463🗒️ 문제 설명정수 X가 할 수 있는 연산X가 3으로 나누어 떨어지면 3으로 나눈다.X가 2로 나누어 떨어지면 2로 나눈다.1을 뺀다.정수 N을 1로 만들려고 할 때, 연산의 최솟값을 구하여라.시간 제한: 1.5초메모리 제한: 128MB1 💡 문제 해결 아이디어N이 최대 1,000,000이기 때문에 시간복잡도가 O(N)이하의 알고리즘을 사용연산 횟수를 저장할 N+1 길이의 배열을 만들어서 사용BFS와 DP를 사용하면 풀 수 있다.# BFS 사용-1을 가지는 N+1 길이의 dist 배열 정의dist[N] = 0으로 초기화queue에 N을 넣고 BFS 수행queue를 popleft()해서 xp를 구한 후 위의 세 연산을 수행한 값이 integer라면 dist[re..

📌 문제 제목문제 링크: BOJ 30804🗒️ 문제 설명1부터 9까지의 과일 N개가 꽂혀있는 탕후루가 있을 때, 앞이나 뒤의 과일을 제거하여 최대 2종류의 과일만을 가지는 탕후루를 만들어라.이때, 탕후루에 꽂혀있는 과일의 최대 개수를 구하여라.시간 제한: 2초메모리 제한: 1024MB1 1 💡 문제 해결 아이디어N이 최대 200,000 이므로 시간복잡도가 O(N)의 알고리즘 사용연속된 구간에서의 과일의 개수를 구하는 문제이므로 투 포인터를 사용다음에 꽂아야 할 과일이 이미 꽂혀있지 않고 이미 종류가 2종류라면 break⌛️ 시간 복잡도O(N)st는 시작점 포인터로 최대 N번 반복en은 끝점 포인터로 전체적으로 N번까지 증가겉보기에는 이중 반복이지만, en은 한 번 증가하면 다시 줄어들지 않음. ->..

📌 문제 제목문제 링크: BOJ 1806🗒️ 문제 설명10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 있을 때, 이 수열에서 연속된 수들의 부분합 중 그 합이 S 이상이 되는 것 중 가장 짧은 것을 구하여라.시간 제한: 0.5초메모리 제한: 128MB10 0 💡 문제 해결 아이디어시간 제한이 0.5초이고 N이 최대 100,000개 이므로 O(N)의 시간복잡도를 가지는 알고리즘을 사용연속된 수들의 부분합을 구하는 문제이므로 투 포인터 사용st를 0으로 잡고 부분합이 S 이상일 때 까지 en을 증가 + total에 부분합을 더하기처음 total이 S 이상일 때 answer을 비교 후 갱신total에 seq[st] 감소⌛️ 시간 복잡도O(N)st는 최대 N번 반복en은 전체 루프 동안 N번까지 ..

📌 문제 제목문제 링크: BOJ 2230🗒️ 문제 설명N개의 정수로 이루어진 수열이 있을 때, 이 수열에서 두 수를 골랐을 때 그 차이가 M 이상이면서 제일 작은 경우를 구하여라.시간 제한: 2초메모리 제한: 128MB1 0 0 💡 문제 해결 아이디어N이 최대 100,000 이기 때문에 O(N log N) 이하의 시간복잡도를 가지는 알고리즘 사용정렬을 시킨다면 st가 증가할 때 en이 줄어들 수 없으므로 O(N)의 시간복잡도를 가지는 투 포인터를 사용할 수 있다.입력이 정렬되어 있지 않으므로 수를 정렬 - O(N log N)st를 0으로 잡고 두 수의 차가 M 이상일 때까지 en을 증가시킴.처음 M 이상인 지점에 두 수의 차를 answer과 비교⌛️ 시간 복잡도O(N log N)정렬에 O(N log..