https://www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 2차원 배열 cache에, cache[x][y] = x, y가 오른쪽 아래인 정사각형의 한 변의 길이를 저장하여, 문제를 해결했다. 먼저 정사각형의 한 변의 길이가 1인 것을 DP 테이블에 채우고, 이를 이용해 bottom-up 방식으로 DP 테이블을 채워 나갔다. 코드 #include #include #include #include using namespace std; int n, m; int cache[1005][1005]; //[x][y] = x,y가 오른쪽 아..

https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net cache[s][e]에, s~e 범위가 팰린드롬인 경우 1, 아닌 경우 0을 저장하여 bottom up 방식으로 다이나믹 프로그래밍을 진행하여, DP 테이블을 채우고, 해당 값을 기반으로 질문에 대한 답을 구했다. 코드 #include #include #include using namespace std; int n, m; int number[2005]; int cache[2005][2005]; //[s][e] = s~e 범위가 팰린드롬..

https://www.acmicpc.net/problem/22944 22944번: 죽음의 비 가로, 세로 길이가 $N$인 정사각형 격자가 있다. 해당 격자에는 두 곳을 제외한 모든 곳에 체력을 1씩 감소시키는 죽음의 비가 내리고 있다. 죽음의 비가 안내리는 곳은 현재 있는 위치와 안전지 www.acmicpc.net 시작 지점에서 도착 지점(안전지대)까지 bfs(너비 우선 탐색)을 통해 이동한다, 이때, 이동하려는 위치에 저장된 값보다 체력+우산내구도 값이 더 큰 경우가 일 때 해당 위치를 bfs의 큐에 넣는 방법으로 문제를 해결했다. 코드 #include #include #include #include #include #include using namespace std; int n, h, d; vecto..

https://www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 초기값에서 bfs(너비 우선 탐색)을 통해 최종 값으로 가는 최소한의 명령어를 구했다. 코드 #include #include #include #include #include using namespace std; int t; string a, b; vector output; string solve(int a, int b) { vector discovered(10005, "-1"); qu..

https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 퀸은 상, 하, 좌, 우, 대각선 모든 방향으로 원하는 만큼 이동 가능하므로, 기본적으로 각 행에는 퀸이 하나씩 있어야 하는 건 명확하므로, 각 행에 퀸을 하나씩 두면서, 행에 어떤 열에 둘지 확인한다. 열을 고를 때, 그 열에 두면 이전에 두었던 퀸과 공격할 수 있는 위치에 있지 않은지 확인하면서 해당 열에 둘 수 있는지 확인했다. 코드 #include #include #include using namespac..

https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net cache1[i] 에 앞에부터 a[i]를 마지막으로 끝나는 수열 중 가장 긴 증가하는 수열의 길이를 저장하고, cache2[i] 에 뒤에부터 a[i]를 마지막으로 끝나는 수열 중 가장 긴 증가하는 수열의 길이를 저장한다. 이때 cache1,2를 채우는 방법은 bottom-up DP를 통해 채워나갔다. 그리고 만든 cache1과 cache2를 이용해서 가장 긴 바이토닉 부분 수열을 구했다. 코드 #include #in..