백준문제풀이/DP
14501번-퇴사
문제 https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 접근방법 1) 접근 사고 상담을 할 것인지 안 할 것인지 두 개의 경우를 비교해주면 되는 문제였습니다. 구현 논리는 주석으로 자세하게 참조하였습니다. 2) 시간 복잡도 DP를 활용하여 O(logn)으로 해결이 가능합니다. 3) 배운 점 무난한 문제였던거 같습니다. 4) PS 정답 코드 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 31 32 33 34 35 36 37 38 39 40 41 42 43 44 #include #defin..
2096번-내려가기
문제 https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 접근방법 1) 접근 사고 모두 입력받아서 갱신할 필요없이 값을 입력받은 뒤에 받은 순간마다 판단해주면 되는 문제입니다. 2) 시간 복잡도 3) 배운 점 4) PS 정답 코드 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 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 #incl..
2225-합분해
문제 https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 접근방법 1) 접근 사고 n의 개수가 200으로 한정되있고 시간은 2초라 각각의 경우를 전부 탐색하는 형식의 완전제곱 탐색을 할 경우 시간초과가 발생함 2) 시간 복잡도 O(n^3) 3) 배운 점 배열의 각각의 위치 인덱스에 의미를 부여해서 값을 찾는 형식의 점화식을 세웠다. 4) PS 정답 코드 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 31 32 33 34 35 36 37 38 39 #include #define ..
17069번-파이프 옮기기2
문제 https://www.acmicpc.net/problem/17069 17069번: 파이프 옮기기 2 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 접근방법 1) 접근 사고 이 문제는 파이프를 둘 수 있는 경우에 대한 재귀와 각 조건에 대한 칸을 확인해보면서 재귀함수를 진행하면 되는 문제입니다. 2) 시간 복잡도 다이나믹 프로그래밍으로 접근 및 메모리제이션을 활용하여 O(nlogn) 3) 배운 점 DP + 간단한 구현 알고리즘 문제인거 같다. 4) PS 정답 코드 1 2 3 4 5 6 7 8 9 10 11 12 ..
11727번-2*n 타일링2
문제 https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 접근방법 1) 접근 사고 11726번과 유사하다 가로만 봐주기 때문에 n - 2인 경우를 하나 더 더 해주면 된다. 왜냐하면 2*2 타일의 가로는 2이기 때문이다. 2) 시간 복잡도 O(n) 3) 배운 점 11726번 응용 정도인거 같다. 4) PS 정답 코드 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 31 32 33 3..
11726번-2*n 타일링
문제 https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 접근방법 1) 접근 사고 가로만 봐주면 되는 문제이다. 왜냐하면 가로를 2간 채워서 넣을 것인지 1칸 채워서 넣을 것인지만 봐주면 되기 때문이다. 2) 시간 복잡도 O(n)으로 해결 간으! 3) 배운 점 배열에서 인덱스를 계산해주는 문제와 유사한거 같다. 규칙을 찾아서 점화식을 만들어 푸는 방법도 존재한다. 4) PS 정답 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19..
1932번-정수 삼각형
문제 https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 접근방법 1) 접근 사고 배열이 주어지고 재귀함수를 y,x의 인덱스 값을 가지고 이동시키면서 비교연산을 통해 큰 값을 반환해주면 되는 문제였습니다. 저는 탑다운 형식으로 구현하였습니다. 2) 시간 복잡도 O(n)에 해결되는 문제였습니다. 3) 배운 점 배열에서 인덱스를 통한 이동값을 구하는 문제가 간혹 출제되는거 같은데 일종의 틀이 정해져 있는거 같아서 유형을 복습하기에 좋았습니다. 4) PS 비슷한 유형의 문제를 풀다가 const int max를 통한 배열값 지..
1890번-점프
문제 https://www.acmicpc.net/problem/1890 1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net 접근방법 1) 접근 사고 문제에서 "반드시 오른쪽이나 아래쪽으로만 이동해야 한다. 0은 더 이상 진행을 막는 종착점이며, 항상 현재 칸에 적혀있는 수만큼 오른쪽이나 아래로 가야 한다." 라는 힌트로 두 가지의 경우로 나뉘며 재귀함수로 코드를 작성하면 구현이 쉬울 거 같은 설명이 적혀있다. 2) 시간 복잡도 다이나믹 프로그래밍을 활용하여 접근하였으므로 O(n)의 시간복잡도를 가진다...
1912번-연속합
문제 https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 접근방법 1) 접근 사고 처음에는 이분탐색으로 구현을 할 려고 했었다. 그러나 이분탐색 부분을 구현하던 도중 두 개의 값을 더 한것을 어떻게 표현할 것인지에 대해 막혀서 다시 고민을 했었고 두 개를 더할 것인가 말 것인가에서 DP로 점화식을 세우면 될 것 같다고 생각을 하였다. 2) 시간 복잡도 DP로 구현을 하였으므로 시간초과 관련 문제는 없었다. 자료형도 최대 100,000 * 1000 = 1,00..
1463번-1로 만들기
문제 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 접근방법 1) 접근 사고 X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 이런 형식으로 문제에서 재귀함수로 구현하면 구현하기 쉽게 힌트를 준다. 이런 방식을 완전탐색으로 풀려고 접근하여 각각의 경우에서 수 많개의 경우의 수로 분할 되기 때문에 시간초과가 나므로 시간복잡도를 줄여야 하는 문제임을 알 수 있다. 2) 시간 복잡도 memorization 기법을 사용한 DP로 접근 3) 배운 점 memorization을 활용해서 탑다운 방식의 알고리즘을 구현해..
9461번-파도반수열
문제 https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 접근방법 1) 접근 사고 문제에서 보면 누가봐도 규칙을 찾으라고 예시까지 친절하게 준다. 2) 시간 복잡도 완전탐색으로는 구현할 방법이 떠오르지 않는 문제. 삼각형의 예시를 보면서 점화식을 찾아야 하는 문제이다. 3) 배운 점 문제에서 n은 100까지 인데 문제를 보면서 규칙을 찾다보면 점화식이 cache[n] = cache[n - 2] + cache[ n - 3]인걸 알 수 있다. 그러므로 숫자..
1003번-피보나치함수
문제 https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 접근방법 1) 접근 사고 피보나치 함수에서 재귀되는 경우에 0과 1이 몇 번 나오는지 물어보는 문제이나 반복된 재귀를 사용할 경우 시간초과 발생 2) 시간 복잡도 시간복잡도를 줄이기 위해 공통된 규칙이 있는 DP 방법을 탐색 n= 0 일 때 zero는 1개 나오고 one은 0개 나온다 n= 1 일 때 zero는 0개 나오고 one은 1개 나온다 n= 2 일 때 zero는 1개 나오고 one은 1개 나온다 n= 3 일 때 zero는 1개 나오고 one은 2개 나온다 n= 4 일 때 zero..