알고리즘(43)
-
백준 16928번: 뱀과 사다리 게임 (C++)
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를 이용했다. 뱀과 사다리에 접근했을 때 pair를 이용하면 전체 탐색을 해야할 것 같아서 map을 이용해 뱀 혹은 사다리에 키 값이 존재하면 바로 이동지점으로 갈 수 있게 했다. 다음 위치가 100 이상이면 탐색하지 않고 100일 때 방문 횟수를 체크하고 BFS를 종..
2023.02.17 -
백준 9047번: 6174 (C++)
https://www.acmicpc.net/problem/9047 9047번: 6174 입력은 표준입력(standard input)을 통해 받아들인다. 입력의 첫 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스마다 한 줄에 네 자리 수(1000~9999)가 하나씩 주어진다. 단, www.acmicpc.net 풀이 단순한 구현 문제 6174가 나올 때 까지 while문을 돌려주면서 cnt를 하나씩 더해주었다. 4자리 숫자가 나오기 때문에 arr[4] 배열을 선언해서 한 자리씩 숫자를 넣어주고 정렬한 다음 최솟값에는 0번부터 3번까지 차례대로 넣어주었고 최댓값에는 3번부터 0번까지 차례대로 넣어주었다. 10을 곱해가며 자릿수를 늘려주면 최대 4자리의 최솟값과 최댓값이 된다..
2023.02.17 -
백준 15988번: 1, 2, 3 더하기 3 (C++)
https://www.acmicpc.net/problem/15988 15988번: 1, 2, 3 더하기 3 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 DP 문제 유형 까먹을 것 같아서 오랜만에 풀어봤다. 매번 하던 재귀 방식으로 구현 했다. 우선, cache 배열을 만들어서 ret 으로 참조하도록 했고, N == 0 이 될 때까지 1, 2, 3을 뺀 케이스를 재귀로 호출과 함께 ret 에 더해주었다. 사실 나도 반복학습으로 배운 방법이라 설명이 어렵다. 전체 코드 #include #include #include using namespace std; const int MOD = 1000000..
2023.01.31 -
백준 3187번: 양치기 꿍 (C++)
https://www.acmicpc.net/problem/3187 3187번: 양치기 꿍 입력의 첫 번째 줄에는 각각 영역의 세로와 가로의 길이를 나타내는 두 개의 정수 R, C (3 ≤ R, C ≤ 250)가 주어진다. 다음 각 R줄에는 C개의 문자가 주어지며 이들은 위에서 설명한 기호들이다. www.acmicpc.net 풀이 울타리 안의 양과 늑대 마리 수를 비교하는 게 중요한 문제. BFS, DFS 어떤 것으로 풀어도 상관 없는데 난 BFS로 풀었다. (앞으로는 구현하기 쉬운 DFS로 풀어야지) 양이 있는 곳을 찾아 그 부분에서 탐색을 진행했다. goY[4] 와 goX[4] 배열을 만들어서 4 방향으로 뻗어나가는 방식으로 진행했고 마을을 벗어나거나 울타리인 경우, 그리고 방문한 경우는 다음 방향을 ..
2023.01.31 -
백준 1259번: 팰린드롬수 (C++)
https://www.acmicpc.net/problem/1259 1259번: 팰린드롬수 입력은 여러 개의 테스트 케이스로 이루어져 있으며, 각 줄마다 1 이상 99999 이하의 정수가 주어진다. 입력의 마지막 줄에는 0이 주어지며, 이 줄은 문제에 포함되지 않는다. www.acmicpc.net 풀이 문자열 / 2 사이즈 만큼 반복문을 돌렸고 앞이랑 뒤 하나 씩 체크했을때 다른게 있다면 chk 에 false를 넣어주었다. 1 2 3 4 2 1 1 2 3 4 2 1 1 2 3 4 2 1 -> 3 과 4가 달라서 chk = false 이런식으로 빨간색끼리 비교해서 다른 것을 체크했다. 전체 코드 #include #include using namespace std; int main() { ios_base::s..
2023.01.26 -
백준 1018번: 체스판 다시 칠하기 (C++)
https://www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 풀이 완전 탐색 문제. 전부 체크해야만 알 수 있는 문제인데 체크 방법을 고민했다. 나는 B로 시작하는 체스판과 W로 시작하는 체스판을 미리 만들어 놓고 비교하는 식으로 구현했다. 어처피 8 * 8이라서 시간 복잡도 문제가 생기지 않을 거 같았고 B, W 보드와 비교 후 둘 중 작은 값을 갱신해가며 탐색을 진행했다. 전체 코드 #include #include using namespace s..
2023.01.26