반갑습니다!

5557번: 1학년 boj.kr 풀이 동적계획법으로 해결해야하는 문제이다. 문제를 읽고 단순하게 생각하면 DFS를 사용해서 해결할 수 있을 것 같지만, DFS를 사용하면 최대 O(2^100)의 복잡도를 가지기 때문에 시간초과가 발생한다. 따라서 다른 방법을 고민해봐야하는데, 문제에 중간에 나오는 수 모두 0 이상 20 이하라는 말이 나온다. 이 점을 이용해서 dp[숫자 인덱스][중간의 나오는 수]는 숫자 인덱스까지 수를 더했을 때 중간의 나오는 수가 될 수 있는 가지수를 구할 수 있다. 코드 C++

1915번: 가장 큰 정사각형 boj.kr 풀이 이 문제는 동적 계획법을 사용해야한다. 이 문제의 핵심 아이디어는 위에서부터 탐색하면서 최대 크기의 정사각형을 갱신하는 것이다. 즉 dp[i][j] = (j, i)에서의 최대 정사각형의 길이가 된다. (수학에서 사용하는 좌표계를 기준으로 x, y 순으로 좌표를 표현했음을 참고할 것) 배열을 board[][]라고 하겠다. 그러면 board[i][j]가 1인 곳은 변의 길이가 1인 정사각형이다. 변의 길이가 2인 정사각형은 board[i][j], board[i-1][j], board[i][j-1], board[i-1][j-1]이 모두 1이어야 한다. 이 문제의 풀이는 여기서 힌트를 얻을 수 있다. 아래의 예시를 보면서 좀 더 알아보자. (0, 0 ~ 3, 0)..

2302번: 극장 좌석 boj.kr 풀이 VIP 회원들에 대해 생각하기 전에 일반 회원들을 먼저 생각해보자. 우선 1명의 회원이 좌석에 앉는 방법을 생각해보자. 1명의 회원이 앉을 수 있는 방법은 1가지인 것은 당연할 것이다. 이번엔 2명의 회원이다. 1, 2 / 2, 1 이렇게 총 2가지 방법으로 앉을 수 있다. 다음엔 3명의 회원인 경우이다. 1, 2, 3 / 1, 3, 2 / 2, 1, 3 총 3가지 방법이 나온다. 4명의 회원의 경우는 1, 2, 3, 4 / 1, 2, 4, 3 / 1, 3, 2, 4 / 2, 1, 3, 4 / 2, 1, 4, 3으로 총 5가지가 나온다. 4명의 회원인 경우를 조금 더 자세히 살펴보자. 1, 2, 3, 4 1, 2, 4, 3 1, 3, 2, 4 2, 1, 3, 4 ..

2096번: 내려가기 boj.kr 풀이 전형적인 동적계획법 문제이다. 하지만 이 문제는 메모리 초과를 조심해야한다. 일반적인 동적계획법을 풀 때 처럼 dp 배열을 생성하면 메모리 초과로 오답을 받게 된다. 그래서 아래의 코드에서는 입력받을 때마다 최대값, 최소값을 저장하는 dp 배열을 갱신해줘서 해결했다. 코드 C++ #include #include using namespace std; int n; int dp[3][2]; int main() { cin >> n; for (int i = 0; i > a >> b >> c; int t1 = dp[0][0]; int t2 = dp[1][0]; int t3 = dp[2][0]; int t4 = dp[0][1..

11060번: 점프 점프 boj.kr 풀이 BFS와 동적계획법을 사용해서 해결했다. 현 위치에서 가장 멀리 뛴다고해서 최적해가 되지 않는다. 따라서 현 위치에서 뛸 수 있는 위치들을 모두 queue에 넣어줘서 최소값을 구했다. 코드 C++ #include #include #include using namespace std; int n; vector a, visited; int bfs() { visited = vector(n, 987654321); queue q; q.push(0); visited[0] = 0; while (!q.empty()) { int cur = q.front(); q.pop(); for (int i = 1; i = n) break; // 범위를 벗어나면 멈춘다 if (visited[c..