1. 문제 https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 2. Error Point 이중 반복문을 빠져 나오는 경우에서 생각하기 오래 걸렸다. flag 변수를 하나 두어서 이중 반복문을 빠져 나오는 것이 아닌 실제 값을 더하는 부분에서 처리하자 3. 풀이 Point 도시의 좌표, 인구 수를 멤버 변수로 가지는 static class를 만든다. 주요 변수 및 자료구조 visited 배열 : BFS 탐색을 위한 방문 배열 cityL..
1. 문제 https://www.acmicpc.net/problem/17135 17135번: 캐슬 디펜스 첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다. www.acmicpc.net 2. Error Point (1) 같은 적이 여러 궁수에게 공격당할 수 있다. 문제에서는 궁수의 공격으로 제거할 수 있는 적의 최대 수를 요구한다. 처음 드는 생각은 최대 수가 나오려면 최대한 겹치지 않게 공격을 해야한다고 생각했다. 그러면 중복으로 적을 고르는 경우는 어떻게 처리해줘야하지??? → 궁수 별로 적을 처치한 수를 카운트 하는 것이 아니기에 내 이전 궁수가 적을 골랐다면 나는 그 적을..
1. 문제 https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 2. 풀이 Point 파이프의 상태에 따라 움직일 수 있는 경우가 다르기 때문에 이를 분기점으로 나눠주는 것이 중요 파이프의 상태에 따라 switch case로 나누어 주었고 파이프의 상태에 따라 갈 수 있는 경우를 재귀 함수를 통해 탐색 반복적으로 나오는 경우가 많으므로 이동하는 건 함수로 처리 뒤로 돌아오거나 갔던 곳을 다시 가는 경우는 없기에 visited..
1. 문제 https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 2. 풀이 Point 두 문자열을 입력 받아서 표를 그려보았다. 표의 값은 맨 앞에서부터 탐색하는 지점까지 문자열을 비교하여 최대 몇 개가 겹치는지를 적었다. 예를 들어, 그림의 파란색의 경우 CA와 A를 비교한다. 이때는 최대 겹치는 구간이 A 하나이므로 1을 적는다. 그림의 초록색의 경우 CAPC와 AC를 비교한다. 이때는 최대 겹치는 구..
1. 문제 https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 2. Error Point 없애야 하는 전깃줄 수를 구하기 위해 입력받은 전깃줄을 탐색하면서 하나라도 교차하면 카운트하는식으로 생각함 → 이 후 어찌 처리해야 하는지 감이 안옴 없애야 하는 전깃줄의 최소 개수를 구하기 위해 반대로 생각하여 전체 전깃줄 수 - 교차하지 않는 최대 전깃줄 수 = 없애야 하는 전깃줄의 최소 개수. 즉 교차하지 않는 최대 전깃줄 수를 구하고 전체 전깃줄 수에서 빼주면..
1. 문제 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 2. 풀이 Point 각 행 별로 선택할 수 있는 경우의 수는 세 가지다. (첫 번째, 두 번째, 세 번째) 그리고 각 경우의 수를 선택했을 때 다음을 고를 경우의 수는 세 가지이다. 따라서 0번 열, 1번 열, 2번 열을 각각 메모이제이션 해주어야 하므로 dp를 2차원 배열로 만든다. 각 경우의 수를 골랐을 때의 최대 값은 다음과 같은 형식으로 식을 세울 수 있다. 최소 값도 이와 마찬가지로 N -..
1. 문제 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 2. 풀이 Point (1) 벽을 만날 때마다 벽을 부수고 bfs 돌리는건 시간 초과가 난다. 벽을 탐색한다면 NM의 시간이 걸리고 이에 대하여 각각 bfs로 탐색하므로 (NM)^2의 시간이 걸린다. (2) 벽을 부쉈는지 안 부쉈는지 객체 안에 flag 변수를 두거나 visited 배열을 boolean으로 두는 경우는 탐색을 할 수가 없거나 잘못된 값을 반환한다..
1. 문제 https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 2. 풀이 Point dp[p] = r p의 수를 만들 수 있는 경우의 수 r 1 동전만 썻을 때의 개수, 1과 2 동전을 썻을 때의 개수, 1과 2와 5 동전을 썻을 때의 개수를 행렬로 그린다. 2가 있는 row의 경우 1과 2를 사용해서 1을 만들 수 있는 경우의 수를 의미한다. 하지만 2를 사용해서 1을 만들 수 있는 경우는 없으므로 1로만 만들 수 있는 경우의 수가 그대로 내려간다..
