https://www.acmicpc.net/problem/1446 1446번: 지름길 첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하인 양의 정수이고, D는 10,000보다 작거나 같은 자연수이다. 다음 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이 www.acmicpc.net 1. Logic 문제를 보자마자 직관적으로 같은 지점을 지나가야하는 중복 문제가 보여서 DP로 접근했다. 2. Code #include using namespace std; int n, d; vector arr[10001]; int dp[10001]; int solve(int location) { if(location == d) return 0; int &ret = dp[location..
Algorithm/Beakjoon
https://www.acmicpc.net/problem/2665 2665번: 미로만들기 첫 줄에는 한 줄에 들어가는 방의 수 n(1 ≤ n ≤ 50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다. www.acmicpc.net 1. Logic vis 배열에 해당 좌표까지 오는데 바꾼 최소 방의 갯수를 저장하면서 다익스트라와 비슷한 방식으로 풀이해주면 된다 2. Code #include using namespace std; int n; int graph[51][51]; int vis[51][51]; int dx[4] = {-1, 0, 1, 0}; int dy[4] = {0, -1, 0, 1}; void bfs() { qu..
https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 1. Logic 같은 위치에 파이프가 위치할 수 있기 때문에 중복 문제가 생기므로 DP를 사용해서 풀이했다. 이 문제에서 주의할 점은 지문에서 "꼭 빈 칸이어야 하는 곳은 색으로 표시되어져 있다." 라는 문장을 잘 읽어야한다. 가로와 세로는 단지 가는 가는 곳만 벽이 아니면 되지만, 대각선 파이프는 옮기는 지점에서 왼쪽, 위쪽이 비어있어야 한다. 이 부분만 잘 짚고 넘어가..
https://www.acmicpc.net/problem/9328 9328번: 열쇠 상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 www.acmicpc.net 1. Logic 방에 들어갈 때 .이나 $이면 들어갈 수 있기 때문에 방 주변을 이동 가능한 공간으로 둘러싸서 입구를 찾아준다. BFS함수 안에서 각 열쇠마다 키가 없을 때 방문했던 좌표를 queue에 저장해놓고 키를 찾으면 queue에서 뽑았던 좌표를 빼서 확인해준다. 아이디어가 신박했다. 2. Code #include using namespace std; int dx[4] = {-1, 0, 1, 0}; i..
https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 1. Logic 먼저 이 문제를 풀기 위해서는 2차원 배열에서 누적합을 구하는 방법을 알아야 한다. 2차원 배열에서 누적합을 구하는 점화식을 먼저 보자 prefixSum[i][j] = prefixSum[i][j] + prefixSum[i-1][j] + prefixSum[i][j-1] - prefixSum[i-1][j-1] 예시로 (2,2)의 누적합을 구하..
https://www.acmicpc.net/problem/11066 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net 1. Logic DP를 푸는 방법은 늘 그렇듯 부분문제를 쪼개는게 핵심이다. 이 문제에서 부분문제를 생각해보면 파일을 어떻게 나눌건지를 생각해야된다. 문제에서 나온 테스트케이스를 보면 40 30 30 50이다. 여기서 파일의 순서를 임의로 바꿀 수 없는것을 유의하면 부분문제는 총 3가지로 볼 수 있다. 나누는 부분을 보면 아래와 같다. 40 / 30 30 50 40 30 / 30 50 4..
https://www.acmicpc.net/problem/2167 2167번: 2차원 배열의 합 첫째 줄에 배열의 크기 N, M(1 ≤ N, M ≤ 300)이 주어진다. 다음 N개의 줄에는 M개의 정수로 배열이 주어진다. 배열에 포함되어 있는 수는 절댓값이 10,000보다 작거나 같은 정수이다. 그 다음 줄에는 www.acmicpc.net 1. Logic 11066번 파일합치기 DP문제를 풀다가 누적합이라는 개념을 알게되어 공부할 겸 풀어봤다. 물론 이문제는 누적합 없이도 풀리긴 한다. 아래 행렬의 누적합을 구해보자 y\x 1 2 3 1 1 2 4 2 8 16 32 나는 처음에 행렬의 누적합은 당연히 다 1,1에서 해당 좌표까지 다 더하는 줄 알았다 그래서 내가 생각한 누적합은 아래와 같았다ㅋㅋㅋㅋ y\..
https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 1. Logic 단순 BFS를 돌아서 갯수를 세주면 된다. 2. Code #include using namespace std; int graph[101][101]; bool vis[101][101]; int dx[4] = {-1, 0, 1, 0}; int dy[4] = {0, -1, 0, 1}; int n, m, k; int bfs(int yy, int xx) { queue q..
https://www.acmicpc.net/problem/17244 17244번: 아맞다우산 경재씨는 저녁 약속을 가기 전 챙기지 않은 물건들이 있는 지 확인하고 있다. 필요한 물건은 전부 챙긴 것 같았고 외출 후 돌아오는 길에 경재씨는 외쳤다. "아 맞다 우산!!!" 경재 씨는 매번 외출 www.acmicpc.net 1. Logic 입력을 받은 후 물건이 있는 좌표를 받으면 0~5까지의 char타입으로 변경해서 넣어줬다. BFS를 돌면서 입력 받을 때 char타입으로 변경해서 넣어준 물건을 만나면 다시 int타입으로 변경해서 shift연산을 통해 비트계산을 해서 몇번째 물건을 집었는지 기록한다. BFS를 돌면서 E(출구)를 만났을 때 내가 받은 물건과 도착한 시점에서의 물건갯수가 일치하면 걸린시간을 리..
https://www.acmicpc.net/problem/1194 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, www.acmicpc.net 1. Logic 열쇠가 6개밖에 없기때문에 비트로 표현 가능하다. 큐에 현재 열쇠를 모은 상태를 비트로 저장해서 관리해준다. 이 문제에서 나눠질 부분문제를 생각해보면 1. 열쇠를 만날경우 - 현재 열쇠를 모은거와 지금 열쇠를 or연산하여 모은 상태를 구하고 모았던 열쇠면 다시 갈 필요 없기 때문에 건너뛰고 안모은 열쇠면 갱신한 열쇠 컬렉션 상태를 큐에 넣어준다. 2...
