문제 https://www.acmicpc.net/problem/1436 1436번: 영화감독 숌 666은 종말을 나타내는 수라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타워 www.acmicpc.net 풀이 문제 설명을 처음 읽었을 때는 너무 간단해보여서 쉬울 줄 알았던 문제이다. 그러나, 실제로 코드로 구현을 하려고 하니 생각보다 어려워서 시간이 좀 걸렸다. 666을 포함한 수를 작은 순서대로 나열하여 N번째 수를 출력하는 문제이다. 666을 포함한다는 것을 코드로 어떻게 표현할지 고민했다. 예를 들어, 1666, 6665, 123666, 436667과 같은 수는 모두 666을 포함하고..
전체 글
문제 11057번: 오르막 수 (acmicpc.net) 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 풀이 문제를 처음 보았을 때 dp로 풀어야겠다고 바로 생각이 든 문제이다. dp로 접근은 했지만, 점화식을 찾는 과정에서 시간이 오래 걸렸다. 일단, 2차원 dp 배열을 선언했다. dp[i][j] : 길이가 i 이면서, j 라는 숫자로 끝나는 수 ex) dp[2][3] : 길이가 2이면서, 3으로 끝나는 수 -> 03, 13, 23, 33 일단, 길이가 1인 경우에는 숫자가..
문제 출처 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 구현 방법 1. 이차원 배열 형태의 input이 주어지고, 문제를 읽어보았을 때, DFS나 BFS와 같은 그래프 순회 알고리즘을 사용해야 한다는 것을 직관적으로 알 수 있다. 2. DFS를 사용할지, BFS를 사용할지 선택을 해야 한다. -> 단순히 시작점부터 도착점까지 그래프를 순회하는 유형의 문제에서는 DFS를 사용하든 BFS를 사용하든 상관 X (최단 거리가 보장되..
[백준 2630] 색종이 만들기 문제 출처 https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 문제 접근 방법 ㆍ해당 문제는 분할 정복과 관련된 문제이다. ㆍ분할 정복은 큰 문제를 작은 문제로 분할하여 해결하는 방법이다. ㆍ그 중에서도 재귀를 사용하여 푸는 것이 좋겠다고 생각했다. 코드 #define _CRT_SECURE_NO_WARNINGS #include #include using namespace std; int a..
문제 출처 https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 문제 접근 방법 ㆍ적어도 M미터의 나무를 가져갈 수 있는 높이의 최댓값을 찾아야 한다. ㆍ어쨌든 값을 찾는 방식의 문제이기 때문에 '탐색'을 이용하는 것이 좋겠다는 생각을 했다. ㆍN은 100만까지 가능하고, M은 20억까지 가능하기 때문에, 굉장히 큰 수이므로, 선형 탐색으로 구현하게 되면 시간 초과 가 날 것이라고 생각을 했다. ㆍ그래서 이분 ..
백준 1158번 (요세푸스 문제) 문제 출처 https://www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 문제 문제 접근 방식 요세푸스 문제는 queue를 이용하였다. N명의 사람이 원을 이루며 앉아있는 상황으로 주어지는데, 원으로 생각하는 것보다 queue를 이용하기 위해 일렬로 나열되어 있는 상황으로 생각하는 것이 더욱 접근하기 쉽다. 또한, K번째 사람을 제거하는 방식은, 맨 처음 사람부터 K - 1번째 사람을 맨 뒤로 보내주면 기존에 K번째에 있던 사람이 가장 처음 위치에 오게 되고, 즉 queue의 가장 첫번째 원소가 되기 때문에, pop..