2JINISHAPPY 2JINISHAPPY

www.acmicpc.net/problem/2011 2011번: 암호코드 나올 수 있는 해석의 가짓수를 구하시오. 정답이 매우 클 수 있으므로, 1000000으로 나눈 나머지를 출력한다. 암호가 잘못되어 암호를 해석할 수 없는 경우에는 0을 출력한다. www.acmicpc.net 주어진 알파벳 string의 해석 경우의 수를 구하는 DP문제 수를 한 자리, 두 자리 씩 끊을 때 나올 수 없는 숫자의 범위가 있기 때문에 그 경우를 고려해주어야 한다. -2만큼 이전에 있는 인덱스를 참조하기 때문에 base case를 위해 앞에 dummy string을 추가해주었다. #include #include #define MOD 1000000 using namespace std; string str; int dp[50..

www.acmicpc.net/problem/1944 1944번: 복제 로봇 첫째 줄에 미로의 크기 N(4 ≤ N ≤ 50)과 열쇠의 개수 M(1 ≤ M ≤ 250) 이 공백을 사이에 두고 주어진다. 그리고 둘째 줄부터 N+1째 줄까지 미로의 정보가 주어진다. 미로는 1과 0, 그리고 S와 K로 주어 www.acmicpc.net 스터디 문제 풀이용으로 급하게 서치한 문제인데 굉장히 유익한 것 같아서 포스팅 로봇의 시작 좌표 S가 주어지고, 열쇠의 좌표 K(여러 개)가 주어졌을 떄 모든 열쇠를 얻을 수 있는 최단거리 이동 경로를 구해야 한다. 이 때, 이동 경로에는 가중치가 없고(BFS를 이용한 최단거리 계산) 열쇠가 복사가 가능하기 때문(S에서만 K를 도달할 수 있는게 아닌, K에서 다른 K로도 이동 가능..

www.acmicpc.net/problem/2933 2933번: 미네랄 창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유인지를 결정하기로 했다. 싸움은 동굴에서 벌어진다. 동굴에는 미네랄 www.acmicpc.net 삼성 A형 시험과 유사한 문제 우선 예제를 살펴보면 ........ ........ .....xx. ...xxx.. ..xxx... ..x.xxx. ..x...x. .xxx..x. ........ ........ .....x.. ...xxx.. ..xxx... ..x.xxx. ..x...x. .xxx..x. ........ ........ .....x.. ...xxx.. ...xx... ..x.xxx. ..x...x. .xx..

www.acmicpc.net/problem/15684 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 삼성 A형 기출인 사다리 조작 문제 시간을 줄일 수 있는 분기가 많기에 백트래킹 연습에 좋은 문제라고 생각한다. 사다리는 0개~3개를 설치할 수 있다. 따라서 4번의 반복문을 통해 해당 탐색에서 놓을 총 사다리 수를 정하고 백트래킹 루틴을 돌려 주었다. 까다로웠던 점은 해당 stage에 사다리 설치를 완료한 뒤 중복 체크를 막기 위한 다음 stage 선정이 조금 어려웠다. 그래서 처음엔 행 - 열 순서로 검사..

처음에 풀었던 코드 #include #define INF 987654321 char map[10005][10005]; bool visit[10005][10005]; int n, m, ans,dx[] = { 1,1,1 }, dy[] = { -1,0,1 },k=INF,col[10005]; bool safe(int r, int c) { return r >= 0 && r = 0 && c < m; } bool pipe(int r,int c) { if (c == m-1) { visit[r][c] = true; return true; } for (int i = 0; i < 3; i++) { int nr = r + dy[i], nc = c + dx[i]; if (!safe(nr,nc)||map[nr]..

www.acmicpc.net/problem/17135 17135번: 캐슬 디펜스 첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다. www.acmicpc.net 이전의 풀이와는 조금 달라진 점이 있어서 다시 포스팅한다. 2년전에도 조합 구할 때 bound를 M인데 N으로 써놓고 삽질했는데.............. 2년이 지나도 똑같다 ㅎㅎ import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.FileInputStream; import java.io.IOException; import java.io..

www.acmicpc.net/problem/1405 1405번: 미친 로봇 첫째 줄에 N, 동쪽으로 이동할 확률, 서쪽으로 이동할 확률, 남쪽으로 이동할 확률, 북쪽으로 이동할 확률이 주어진다. N은 14보다 작거나 같은 자연수이고, 모든 확률은 100보다 작거나 같은 자 www.acmicpc.net 로봇이 동서남북으로 N번 움직일 수 있다고 할 때, 이동 경로가 단순할 확률(이미 방문한 곳을 방문하지 않을 확률)을 구하는 문제이다. N이 14 이하의 자연수이기 때문에, 최대 4^14(268,435,456)가지의 이동 경우의 수가 나온다. 즉, 1억번 이하이므로 모든 경우에 대해 조사하면서 단순한지 아닌지 검사해주었다. 백트래킹을 이용해서 특정 좌표의 방문/미방문을 갱신해주었고, 서로 다른 좌표를 N개 ..

www.acmicpc.net/problem/16931 16931번: 겉넓이 구하기 크기가 N×M인 종이가 있고, 종이는 1×1크기의 칸으로 나누어져 있다. 이 종이의 각 칸 위에 1×1×1 크기의 정육면체를 놓아 3차원 도형을 만들었다. 종이의 각 칸에 놓인 정육면체의 개수가 주어 www.acmicpc.net 백준의 겉넓이 구하기 문제 기하적인 문제이다 각 칸의 넓이를 1이라 했을 때, 도형의 겉넓이를 구하는 문제이다 이 때, 그림의 흰색 칸은 위에서 투시했을 때의 위쪽 면의 겉넓이이다. 밑에서 봤을 때에도 동일하므로 초기의 겉넓이 값은 N*M*2이다 그리고 옅은 주황색 면을 보면, 요철이 많지만 앞에서 투시해서 봤을 때 반대편에서 봤을 때랑 겉넓이가 같음을 알 수 있다. 따라서 옅은 주황색 면의 겉넓이..