coding tasty house

문제설명 규칙에 알맞게 주어진 입력값에 대해서 구해 낼 수 있는 최대값을 출력한다 계단의 수가 주어지고, 각 계단마다의 값이 주어진다 계단은 한번에 한칸 또는 두칸씩 오를 수 있으며, 세칸연속 밟는것은 불가능하다 그리고 마지막엔 반드시 마지막 칸을 밟아야한다 알고리즘 1. 계단의 각 정보를 입력 받는다 2. 3번째 계단까지 따로 계산해 둔다 3. 반복문을 통해서 n 번째 계단까지 구한다 4. n번째 계단의 값을 구한다 코드 #include #include #include using namespace std; int stair[301]; int dp[301]; int main() { int n; cin >> n; for (int i = 1; i > stair[i]; dp[1] = stair[1]; dp[2..

문제설명 테스트 케이스 수를 입력 받은 뒤, 입력되는 N의 값을 출력 시키면된다. 이 때 각 값의 정의를 보자면, P(1) = 1 P(2) = 1 P(3) = 1 P(4) = 2 P(5) = 2 P(6) = 3 P(7) = 4 P(8) = 5 P(9) = 7 P(10) = 9 값이 나오는 것을 확인할 수 있다. 이 값의 의미는 1번째 삼각형 일때 최대 정삼각형의 변의 길이가 1이라는 뜻이다. 즉 P(10)의 경우 10번째 삼각형을 위의 그림과 같은 규칙으로 그렸을 때 최대 정삼각형의 변의 길이가 9라는 의미이다. 해당 값을 나열해보면 다음과 같은 점화식을 구할 수 있다. P(N) = P(N-3) + P(N-2) 해당 식을 이용하여 코드를 짜면 된다. 알고리즘 1. 점화식을 이용하여 미리 답을 저장할 배열..

평범한 배낭 문제설명 가방의 최대 수용량을 넘지 않는 범위 내에서 가장 가치가 높은 물건을 가져올 때, 최대 가치를 구하자 알고리즘 값을 각각 입력 받는다. 이중 반복문을 사용하는데, 바깥은 가방의 정보를 저장한 index, 안쪽은 무게 K까지 돈다. i번째 가방의 무게를 조회하고 현재 가방의 무게를 넘으면 이전 값, 그렇지 않으면 max함수로 비교하여 dp그래프를 채운다. 배열의 가장 마지막 값을 출력한다. #include #include #include #include using namespace std; #define MAX 100001 #define MAXN 101 int N, K; int dp[MAXN][MAX]; int main() { ios_base::sync_with_stdio(0); ci..

가장 긴 증가하는 부분 수열 문제설명 가장 긴 증가하는 수열의 길이를 구한다. 알고리즘 값을 각각 입력받고 dp의 값을 길이만큼 1로 초기화 해준다. 이중 for문 안에서 arr값을 하나 불러오고 밖의 for문의 인덱스 만큼 다시 0부터 인덱스까지 값을 조회한다. 값을 비교하여 현재 구하고자 하는 곳의 값이 이전의 수열 인덱스 값보다 큰 경우 max값을 찾아서 업데이트한다. 업데이트할 때 현재의 dp값, 그리고 이전의 dp값 중에 가장 큰 값에 1을 더하고 큰 값을 저장한다. dp중에 가장 큰 값이 최장길이이다. #include #include #include #define MAX 1001 using namespace std; int arr[MAX]; int dp[MAX]; int main() { ios..

RGB거리 문제설명 집에 빨강,초록,파랑으로 색을 칠하려 한다. 위의 사진에서 규칙을 확인하고 모든 집을 칠하는 비용의 최솟값을 출력하라. 알고리즘 값을 각각 입력받고 dp의 값을 저장할 부분인 result에 초기 값을 입력 받은 값으로 설정해준다. 반복문으로 나머지 부분을 각 색깔에 맞춰서 해당 색은 사용하지 않은 가장 작은 전 값에 현재 색을 더해준다. N만큼 진행하고 가장 끝 행에 값들 중 가장 작은 값을 출력시킨다. #include #include #include #define MAX 1001 using namespace std; int N; int graph[MAX][3]; int result[MAX][3];//결과 값을 저장하기 위한 배열 int main() { ios_base::sync_wi..

LCS 문제설명 주어진 두 문자열에서 최장 부분 수열을 구해 출력 시킨다. 알고리즘 값을 각각 입력받고 입력 받은 문자열에 편의를 위해 0을 추가해서 붙인다. 각 첫행 첫열은 0으로 초기화한다. 비교하는 기준 문자열에서 같으면 해당 칸의 대각선 값 +1을 표에 넣는다. 비교하는 기준 문자열에서 다르면 왼쪽, 또는 위의 값 중에 더 큰 값을 찾아서 넣는다. 해당 테이블이 가장 오른쪽 아래 값이 정답이 될 수 있다. #include #include #include #include #define MAX 1001 using namespace std; int lcs[MAX][MAX]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); string A,B; cin >..

문제설명 n의 값을 입력 받고 타일로 채우는 방법의 수를 출력하는 문제이다. 단, 출력시 10007로 나눈 나머지를 출력시킨다. 알고리즘 n의 값을 입력 받는다. bottom-up방식으로 배열에 값을 저장 하는데 런타임 에러방지를 위해 10007로 나눈 나머지를 저장한다. 해당하는 값을 출력한다. #include #include using namespace std; int main(void) { ios::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); int N; cin >> N; // n값 입력 int arr[1001]; arr[0] = 1; arr[1] = 2; for (int i = 2; i < N; i++) arr[i] = (arr[i - 1] + arr..

피보나치 함수 문제 설명 피보나치 함수에서 0과 1이 각각 출력 되는지 결과 값을 출력한다. 이때 T의 수만큼 테스트케이스를 반복하고 N(40까지)의 값을 각각 입력 받는다. 알고리즘 배열에 40까지의 예측 값을 저장해 둔다. 테스트케이스와 0일때 1일때 그 외일 때의 경우로 나누어 출력한다. #include #include #include using namespace std; int main() { int T, N; cin >> T; int arr[41] = {0,1,1}; for (int i = 3; i > N; if (N == 0) cout