개발기록 개발기록

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

https://www.acmicpc.net/problem/14890 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net 시뮬레이션 문제입니다. 단순하게 하나하나 구현한다면 복붙한다해도 시간이 걸릴 것 입니다. 보통 이런 문제들은 생각을 살짝 바꾼다면 하나의 모듈에 여러 상황을 담을 수 있습니다. 행 오른쪽 경사로 탐색, 행 왼쪽 경사로 탐색, 열 위쪽 경사로 탐색, 열 아래쪽 경사로 탐색 문제에서 고려해야 할 상황입니다. 행과 열은 회전만 시켜주면 똑같은 것이고 오른쪽, 왼쪽은 뒤집으면 똑같은 것 입니다. 즉, 전처리로 저렇게 해주면 탐..