컴공과고씨

https://www.acmicpc.net/problem/2665 2665번: 미로만들기 첫 줄에는 한 줄에 들어가는 방의 수 n(1 ≤ n ≤ 50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다. www.acmicpc.net 문제 정리 바둑판 모양이 있음. 각 방 마다 지나갈 수 있는 방과 없는 방으로 나뉨. 갈수 없는 방은 뚫 수 있음. (0,0) 에서 (n-1,n-1)까지 가는데 방을 최소한으로 뚫어서 갈 때 몇 개를 뚫어야 하는가? 문제 해결 방법 BFS를 사용해서 탐색을 하는데 각 방 마다 뚫고 온 방의 개수를 적어서 BFS 탐색을 해주면 됩니다. 방의 초기 값은 크게 잡아 줍니다. 그 후 시작점은 0으로 해줍..

https://www.acmicpc.net/problem/20055 20055번: 컨베이어 벨트 위의 로봇 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부 www.acmicpc.net 문제 정리 컨베이어 벨트가 있음 벨트 구성은 이런식으로 벨트는 회전합니다. 올리는 위치에서 로봇을 올리고 내리는 위치에 로봇이 도착하면 로봇을 즉시 내립니다. 또한 벨트마다 내구도가 주어짐. 벨트 작동 순서 1. 벨트가 각 칸 위에 있는 로봇과 한 칸 움직임 2. 벨트에 먼저 올라간 로봇 부터 벨트가 움직이는 방향으로 로봇을 한 칸 움직임 2-1) 움직이는 조건은 다음 칸의 ..

https://www.acmicpc.net/problem/14890 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net 문제 간단 정리 한 행렬이 있을 때 한 행으로 쭉 갈거나 한 열로 쭉 갈 수 있다면 그것은 길이다. 길의 개수를 세야함. 근데 각 좌표에는 높이가 있음. 높이가 다르면 경사로를 설치해서 지나갈 수 있음. 경사로 설치 조건 1. 높이 차는 1이여야함. 2. L이 주어지는데 높이가 낮은 쪽에 L개수 만큼 같은 높이로 좌표가 있어야 설치가 가능함. 3. 경사로는 곂쳐지면 안됨. 문제 해결 방법 일단 행렬이 있을 때 가로 길을..

https://www.acmicpc.net/problem/2343 2343번: 기타 레슨 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net 문제 정리 강의를 녹화해야함. 강의 수 N개, M개의 블루레이에 저장. 이때 강의마다 시간이 주어지는데 강의는 순서대로 녹화해야함. 또한 강의 중간에 끊겨서 녹화하면 안됨. -> 한 강의는 한 블루레이에 끊어지지 않고 있어야함. 이때 블루레이의 크기를 구하는데 최소 크기를 구해야함. 문제 해결 방법 하나하나 크기를 정해서 비교하면 시간이 굉장히 오래 걸리게 됩니다. 그러므로 이분탐색을 이용하여서 시간 단..

https://www.acmicpc.net/problem/6236 6236번: 용돈 관리 현우는 용돈을 효율적으로 활용하기 위해 계획을 짜기로 하였다. 현우는 앞으로 N일 동안 자신이 사용할 금액을 계산하였고, 돈을 펑펑 쓰지 않기 위해 정확히 M번만 통장에서 돈을 빼서 쓰기로 www.acmicpc.net 문제 간단 정리 돈을 통장에서 인출하는 횟수를 정해놓고 씀. 인출한 금액에서 하루 하루 금액을 정해놓고 사용. 인출한 금액을 쓰다가 모자른 경우 남은 금액 통장에 넣고 다시 아까 정해놓은 인출 금액을 꺼내서 씀. 이때 인출하는 금액을 최소가 되도록 구해라. 인출하는 횟수가 문제에서 주어진 횟수보다 크면 안됨. 하지만 인출하는 횟수가 적은 것은 상관없음 이유는 문제에서 인출하는 횟수를 맞추기 위해서 금액..

https://www.acmicpc.net/problem/15684 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 이 문제는 DFS와 백트래킹을 사용하는 문제입니다. 문제 정리 사다리 타기를 하는데 1번 위치가 사다리를 타면 1번 위치로 내려가고 2번은 2번 위치, 즉, i번이 사다리를 탔을 때 결과가 i번이도록 사다리에 가로선을 추가하는 것입니다. 가로선은 최대 3까지 가능하며 가로선을 최소로 하는 사다리를 만드는 것입니다. 문제 해결 방법 사다리 표시 방법 부터 정해야 합니다. 배열로 정의를 할 것이고 ..

https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 문제를 읽어보면 탐색 문제인 것을 알 수 있습니다. BFS를 사용해서 풀었습니다. 전체적인 문제 해결 방법은 수빈이의 위치와 동생의 위치를 확인 후 같지 않다면 수빈이의 위치를 이동시킨 후 큐에 넣어줍니다. 큐가 빌 때까지 반복 해 주면 됩니다. 그러다 처음으로 위치가 같아지면 이제까지 걸린 시간을 저장해줍니다. 그 후 위치가 같고 그 전에 저장해둔 걸린 시간..

https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 이 문제의 핵심은 두 가지로 볼 수 있다. 첫 번째는 팀을 어떤 식으로 구성하는 가. 두 번째는 구성한 팀에서 능력치를 구해 전 팀과 비교. 팀을 구성하는 방법은 중복을 고려해주어야 한다. 팀을 구성하는 방법 - 먼저 한 팀의 인원은 n/2이다. n이 4라고 할 때 한 팀의 인원은 2명 - 01 02 03 12 13 23 이런식으로 구성할 것이다. for (int i = start; i < n;i++){ // 중복 고..

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 이 문제 같은 경우는 탐색 BFS 알고리즘을 이용하면 쉽게 구현이 가능하다. 보드판 100칸 중에 사다리 혹은 뱀이 있을 경우 도착 지점을 적어두고 나머지는 0으로 해서 특수한 경우와 일반 경우를 구별해준다. bfs를 구현할 때는 큐에 좌표와 주사위를 굴릴 때마다 카운트 하는 변수를 넣어준다. 주사위가 1일때 부터 6일때까지 반복해주고 현재 좌표에 더..

https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 문제 해결 방법은 2차원 배열을 이용해서 map을 만들어주고 사과가 있는 칸에는 1을 넣어준다. 입력으로 시간과 방향 정보를 받아 준다. 방향을 바꾸기 전까지 반복문을 돌아줄건데 다음 x좌표와 다음 y 좌표를 구해주고 맵을 벗어나는지 확인해주고 visit을 체크해줄건데 visit은 몸이 있는 좌표에 true를 넣어주는 것이다. 뱀이 사과를 먹는 경우에 몸의 길이가 늘어나는데 이때 큐에 좌표를 넣어주고 v..