개발기록 개발기록

https://www.acmicpc.net/problem/16637 16637번: 괄호 추가하기 첫째 줄에 수식의 길이 N(1 ≤ N ≤ 19)가 주어진다. 둘째 줄에는 수식이 주어진다. 수식에 포함된 정수는 모두 0보다 크거나 같고, 9보다 작거나 같다. 문자열은 정수로 시작하고, 연산자와 정수가 번갈아가면서 나온다. 연산자는 +, -, * 중 하나이다. 여기서 *는 곱하기 연산을 나타내는 × 연산이다. 항상 올바른 수식만 주어지기 때문에, N은 홀수이다. www.acmicpc.net 괄호의 위치를 백트래킹으로 완전 탐색합니다. 이때, 괄호의 갯수도 유의해야 합니다. 괄호의 위치를 정한 후, 수식 계산을 해줍니다. 계산은 괄호 안을 모두 계산을 한다음, 전체 수식을 계산하였습니다. 접근과 설계가 많이 ..

https://www.acmicpc.net/problem/16922 16922번: 로마 숫자 만들기 2, 6, 10, 11, 15, 20, 51, 55, 60, 100을 만들 수 있다. www.acmicpc.net 전형적인 백트래킹 문제입니다. 조합을 만든 후 숫자 중복 체크를 해주면 됩니다. 처음에 순열로 짜서 틀렸다.. #include #include using namespace std; int n; int res; int cal[4] = {1, 5, 10, 50}; bool visit[1001]; void dfs(int dep, int start, int num) { if (dep == n) { if (!visit[num]) { res++; visit[num] = true; } return; } f..

https://www.acmicpc.net/problem/9376 9376번: 탈옥 문제 상근이는 감옥에서 죄수 두 명을 탈옥시켜야 한다. 이 감옥은 1층짜리 건물이고, 상근이는 방금 평면도를 얻었다. 평면도에는 모든 벽과 문이 나타나있고, 탈옥시켜야 하는 죄수의 위치도 나타나 있다. 감옥은 무인 감옥으로 죄수 두 명이 감옥에 있는 유일한 사람이다. 문은 중앙 제어실에서만 열 수 있다. 상근이는 특별한 기술을 이용해 제어실을 통하지 않고 문을 열려고 한다. 하지만, 문을 열려면 시간이 매우 많이 걸린다. 두 죄수를 탈옥시키기 위해서 열어 www.acmicpc.net 탐색 문제입니다. 일반적인 탐색문제와 다릅니다. 가중치가 이동한 거리와 상관없이 문을 연 횟수로 결정됩니다. 또 움직이는 말이 2개 입니다...

https://www.acmicpc.net/problem/2931 2931번: 가스관 문제 러시아 가스를 크로아티아로 운반하기 위해 자그레브와 모스코바는 파이프라인을 디자인하고 있다. 두 사람은 실제 디자인을 하기 전에 파이프 매니아 게임을 이용해서 설계를 해보려고 한다. 이 게임에서 유럽은 R행 C열로 나누어져 있다. 각 칸은 비어있거나, 아래 그림과 같은 일곱가지 기본 블록으로 이루어져 있다. 가스는 모스크바에서 자그레브로 흐른다. 가스는 블록을 통해 양방향으로 흐를 수 있다. '+'는 특별한 블록으로, 아래 예시처럼 두 방향 (수직, www.acmicpc.net 구현, 완전탐색 문제입니다. 빈 칸에는 어느 가스관이 들어갈지 모릅니다. 그래서 완전탐색으로 찾아야 합니다. 그라고 가스관의 모양에 따라서..

https://www.acmicpc.net/source/17861879 로그인 www.acmicpc.net dp문제 입니다. 종만북 dp 반쯤 공부하다가 말았는데, 쉬운 난이도는 커버가 되는 느낌이네요 #include #include #include using namespace std; int n, map[501][501]; int cache[501][501]; int dy[4] = { 1, -1, 0, 0 }; int dx[4] = { 0, 0, 1, -1 }; int dfs(int y, int x) { int &res = cache[y][x]; if (res != -1) { return res; } res = 1; for (int i = 0; i < 4; i++) { int ty = y + dy[i]..

https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5≤N, M≤100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 표시된다. 또한, 각 0과 1은 하나의 공백으로 분리되어 있다. www.acmicpc.net 탐색 문제입니다. 그런데 문제가 있습니다. 내부 공기, 외부 공기의 개념이 존재한다는 것입니다. 내부 공기의 특징을 보면 치즈로 둘러쌓여 있습니다. 즉, 외부 공기에서 bfs를 돌렸을 때 서로 만나지 않습니다. 그렇다면 외부 공기에서 bfs 돌리고 각 치즈를 몇 번 접촉하였는지 저장하여 녹는 처리를 해주면 됩니다. 마침 치즈의 ..

https://www.acmicpc.net/problem/2169 2169번: 로봇 조종하기 첫째 줄에 N, M(1≤N, M≤1,000)이 주어진다. 다음 N개의 줄에는 M개의 수로 배열이 주어진다. 배열의 각 수는 절댓값이 100을 넘지 않는 정수이다. 이 값은 그 지역의 가치를 나타낸다. www.acmicpc.net dp 문제입니다. dp 하수 오브 하수라서 못풀었습니다..ㅠㅠ cache 배열은 중복계산을 방지하기 위해 메모이제이션을 하는 배열입니다. 이 배열이 왜 3차원 배열이 되어야 하는가에 대해 이해가 잘안갔습니다. 그 이유는 (y, x)에 도달할 때, 도달하는 방향에 따라 값이 달라질 수 있고 그에 따라 메모이제이션도 달리 해야하기 때문입니다. 댓글에 자세한 예시와 함께 설명이 있습니다. 제가..

https://www.acmicpc.net/status?user_id=skaduddn&problem_id=1194&from_mine=1 채점 현황 www.acmicpc.net 탐색 문제입니다. 상태에 대한 방문 관리와 키 관리가 포인트인 거 같습니다. 비트마스킹을 모르는 상태에서는 배열 크기를 늘리고 구현 노가다를 해서 풀었습니다. 후에 검색을 통해 비트마스킹으로 풀었습니다. 비트마스킹을 모르시는 분들이 읽으면 좋을 거 같습니다. https://yabmoons.tistory.com/102 #include #include #include using namespace std; struct point { int y, x, cnt; int a, b, c, d, e, f; }; int n, m, sy, sx; c..