Study hard

www.acmicpc.net/problem/17822 17822번: 원판 돌리기 반지름이 1, 2, ..., N인 원판이 크기가 작아지는 순으로 바닥에 놓여있고, 원판의 중심은 모두 같다. 원판의 반지름이 i이면, 그 원판을 i번째 원판이라고 한다. 각각의 원판에는 M개의 정수가 적혀 www.acmicpc.net [풀이] 구현해야할 것 1. 원판 2. 원판 돌리기 3. 인접하면서 같은 수 찾기 4. 원판에 적힌 수의 평균 찾고 평균보다 큰 수에서 1 빼고 작은수에 1 더하기 1. 원판은 2차원 배열 int Circle[][]로 구현하였다. Circle[i][j]는 i번 원판의 j번째 숫자를 의미한다. 2. 돌릴 원판의 번호와 방향과 돌릴 칸 수를 인수로 보내 시계방향 또는 반시계방향으로 해당 원판을 돌리..

www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net [풀이] LCS가 여러가지인 경우에 아무거나 출력하라고 했으므로 가장 긴 LCS를 출력하도록 했다. LCS를 구하는 것은 아래 풀이처럼 하고 string LCS[n][m]를 이용하여 첫번째 문자열의 n번째 문자까지와 두번째 문자열의 m번째 문자까지의 최장 LCS를 저장하도록 했다. 2021/02/24 - [백준/DP] - (c++)백준 9251번: LCS (c++..

www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net [풀이] dp[i][j] = A문자열의 i번째까지, B문자열의 j번째까지 가장 긴 부분 수열의 길이 #include #include //max #include using namespace std; string A, B; int dp[1001][1001]; void DP() { int N = A.size(); int M = B.size(); for (int i = 1;..

www.acmicpc.net/problem/12906 12906번: 새로운 하노이 탑 첫째 줄에 막대 A에 놓여져 있는 원판의 개수와 막대 A의 상태, 둘째 줄에 막대 B에 놓여져 있는 원판의 개수와 막대 B의 상태, 셋째 줄에 막대 C에 놓여져 있는 원판의 개수와 막대 C의 상태가 주 www.acmicpc.net [풀이] bfs를 어떻게 써야하는 지 감이 안잡혀서 다른 분의 풀이를 봤다. 각각 막대를 문자열로 받고, 모든 경우에 대해서 bfs를 하는 거였다. 모든 경우 1. 막대A에 원판이 한개 이상 있을 때, 막대B에 원판을 하나 주는 경우, 막대C에 원판을 하나 주는 경우 2. 막대B에 원판이 한개 이상 있을 때, 막대A에 원판을 하나 주는 경우, 막대C에 원판을 하나 주는 경우 3. 막대C에 원판..

www.acmicpc.net/problem/2234 2234번: 성곽 첫째 줄에 두 정수 n, m이 주어진다. 다음 m개의 줄에는 n개의 정수로 벽에 대한 정보가 주어진다. 벽에 대한 정보는 한 정수로 주어지는데, 서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, www.acmicpc.net [풀이] 문제 풀이에 대한 감을 못 잡아서 결국 다른 분의 풀이를 참고했다. &연산을 사용하여 벽의 유무를 알아내야 하는 문제였다. Map[i][j] & 1 = 0001이면 (i,j)칸의 서쪽에 벽이 있다는 뜻이다. 마찬가지로, Map[i][j] & 2 = 0010이면 북쪽에 벽이, Map[i][j] & 4 = 0100이면 동쪽에 벽이, Map[i][j] & 8 = 1000이면 남쪽에 벽이 있다는 뜻이다...

www.acmicpc.net/problem/17141 17141번: 연구소 2 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 승원이는 연구소의 특정 위치에 바이러스 M개를 놓을 것이고, 승원이의 신호와 동시에 바이 www.acmicpc.net [풀이] dfs 조합과 bfs flood fill을 사용하여 풀었다. dfs를 사용하여 M개의 바이러스 위치의 조합을 구하고, 각 조합마다 bfs를 사용하여 바이러스가 연구소 전체에 퍼지는 시간을 구하였다. bfs를 호출할 때마다 visited배열을 초기화하고, bfs가 끝나면 최소시간을 갱신해야한다. #include #include #include #include //memset using namespace std; ..