백준

https://www.acmicpc.net/problem/1606 1606번: 침투 계획 세우기 첫째 줄에 멍멍이의 금고의 위치를 나타내는 좌표가 주어진다. 각 수는 0이상 1,000,000이하의 정수이다. www.acmicpc.net 1. Logic x가 0이고 y>0인경우 6*i씩 증가하는 등차수열의 규칙을 가지는 것을 확인할 수 있다. 그리고 모든 입력은 양수로 주어지는 부분에 초점을 맞추면, 1을 제외한 껍질 만큼(x+y) 6을 곱해서 더해주고 만약 y가 0이면 껍질이 하나 생기는 것이기 떄문에 1을 더해준다 2. Code #include using namespace std; int main() { int x, y; cin >> x >> y; long long ans = 1; for(int i =..

https://www.acmicpc.net/problem/17386 17386번: 선분 교차 1 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. 세 점이 일직선 위에 있는 경우는 없다. www.acmicpc.net 1. Logic CCW알고리즘을 활용하여 풀이 가능하다. CCW 알고리즘이란 임의의 선분을 기준으로 다른 한 점이 시계방향으로 위치하는지 반시계방향에 위치하는지 판별할 수 있는 알고리즘이다. 이 알고리즘은 수학시간에 했던 신발끈 공식, 외적을 생각하면 쉽게 이해할 수 있다. 한 선분(선분을 이루는 두 점 A, B)과 다른 한 점(C)을 외적한 값을 CCW(A, B, C)=outer라고 했을 때 outer > 0 : ..

https://www.acmicpc.net/problem/16946 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net 1. Logic 여러가지 방법으로 시도해봤다. 시도한 방법은 1. DFS : DFS로 벽인 부분에서 이동할 수 있는 공간의 크기를 세서 저장했다. 100만개 탐색을 100만번 하니 당연히 터질 수 밖에. 그래서 DP로 접근했다. 2. DP : 한 정점에서 다른 정점으로 가는 방법을 DP로 하면 방향이 일정하기 때문에 값이 구해지지만 이번 문제는 상하좌우를 판단해야 하기 때문에..

https://www.acmicpc.net/problem/2236 2236번: 칩 만들기 당신은 칩을 만들기 위해 기판에 N개의 부품을 장착했다. 각각의 부품을 작동시키기 위해서는 전원을 연결해야 하는데, 기판에 연결할 수 있는 전원 선이 K개 밖에 없었다. 당신은 이 K개의 전원 www.acmicpc.net 1. Logic 선을 하나의 칩에 연결하면 제곱, 두개의 칩에 연결하면 연결한 두 칩의 중요도를 제곱한다. 어떤 경우든 항상 제곱하는게 이득이기 때문에 그냥 정렬해서 큰거만 k개만큼 뽑아주면 된다 풀면서도 이게 맞나 싶었다ㅋㅋㅋㅋㅋㅋ 2. Code #include using namespace std; int n, k; vector input; queue q; int trace[51]; int mai..

https://www.acmicpc.net/problem/1996 1996번: 지뢰 찾기 첫째 줄에 N(1 ≤ N ≤ 1,000)이 주어진다. 다음 N개의 줄에는 지뢰 찾기 map에 대한 정보가 주어지는데 '.' 또는 숫자로 이루어진 문자열이 들어온다. '.'는 지뢰가 없는 것이고 숫자는 지뢰가 있는 경 www.acmicpc.net 1. Logic 단순 파싱 그래프 구현 문제였다. 어렵진 않지만 c++로 파싱하려니 귀찮았다. 2. Code #include using namespace std; int n; int mine[1001][1001]; int sum[1001][1001]; char ans[1001][1001]; int dx[8] = {-1, -1, 0, 1, 1, 1, 0, -1}; int dy[..

https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net 1. Logic dp배열의 의미 : 해당 좌표를 통해 먹을 수 있는 대나무의 최대 갯수 2. Code #include using namespace std; int dx[4] = {-1, 0, 1, 0}; int dy[4] = {0, -1, 0, 1}; int n; int bamboo[501][501]; bool vis[501][501]; int dp[501][501]; int dfs(i..

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..

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..