목록백준 (183)
Study hard
www.acmicpc.net/problem/11048 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 �� www.acmicpc.net [풀이] 진행할수록 범위가 좁아지므로 DP를 사용한다. 어느 방향에서 와야 값이 커지는 지 확인 점화식 DP[i][j] = Maze[i][j] + max(DP[i-1][j], max(DP[i][j-1], DP[i-1][j-1])) #include #include //max using namespace std; int N, M; int Maze[1001][1001]; int DP[1001][1..
https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net [풀이] 1. bfs사용 2. 사다리나 뱀이 있는 칸은 LorS배열에 해당 칸에 도착하면 어느 칸으로 이동하는지를 저장했다. 3. visited배열을 사용하여 한 번 방문했던 칸에 대해서는 다시 탐색하지 않도록 했다.(안 하면 메모리 초과!) #include #include using namespace std; struct Pos { int x; in..
https://www.acmicpc.net/problem/14395 14395번: 4연산 첫째 줄에 정수 s를 t로 바꾸는 방법을 출력한다. s와 t가 같은 경우에는 0을, 바꿀 수 없는 경우에는 -1을 출력한다. 가능한 방법이 여러 가지라면, 사전 순으로 앞서는 것을 출력한다. 연산의 아 www.acmicpc.net [풀이] bfs를 사용했다. 연산의 아스키 코드 순서대로 queue에 푸시해주었기 때문에 값이 t가 되면 바로 그때까지 했던 연산들을 출력하면 된다. set자료구조에 나온 값을 저장하여 같은 값에 대해 더 이상 탐색하지 않게 했다. /연산으로 인해 나오는 1은 처음 한 번만 나오면 되므로 set을 탐색하지 않고 boolean값으로 사용 여부를 체크했다. 사실 -는 쓸일이 없다. (t는 항상..
https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net [풀이] 1. bfs를 사용하여 구역의 수를 구하였다. 2. 적록색약이 아닌 사람의 경우와 적록색약인 사람의 경우를 따로 함수로 구현했다. 3. bfs를 부르는 수 == 구역의 수 #include #include #include #include //memset using namespace std; struct Pos { int x, y; }; int N; int Map[100][100]; ..
https://www.acmicpc.net/problem/1963 1963번: 소수 경로 소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데: “이제 슬슬 비번 바꿀 때도 됐잖아” “응 지금 www.acmicpc.net [풀이] 소수는 에라토스테네스의 체 알고리즘을 이용하여 구하였다. 에라토스테네스의 체 알고리즘은 2부터 구하고자 하는 범위의 수들을 배열에 넣어 소수가 아닌 수를 체크하는 알고리즘이다. 2를 제외한 2로 나누어 떨어지는 값 체크 → 3을 제외한 3으로 나누어 떨어지는 값 체크 → (4는 이미 체크 되었으므로 패스) → 5를 제외한 5로 나누어 떨어지는 값 체크 → ··· 마지막까지 체크되지 않은 값들이 소..
https://www.acmicpc.net/problem/6087 6087번: 레이저 통신 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 www.acmicpc.net [풀이] ※주의 할 것: 최소 거리를 구하는 게 아니라 거울 개수의 최솟값을 구하는 것! - bfs 사용 - visited 2차원 배열에 각 좌표까지 가는 데 놓아야 하는 거울 개수의 최솟값을 저장한다. #include #include #include using namespace std; struct Mirror { int x, y;//설치된 거울 좌표 int d;//방향 int mirr..