본문 바로가기

C++ 코딩 문제 풀이/백준113

[Baekjoon] 1049번: 기타줄 https://www.acmicpc.net/problem/1049 1049번: 기타줄 첫째 줄에 N과 M이 주어진다. N은 100보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에는 각 브랜드의 패키지 가격과 낱개의 가격이 공백으로 구분하여 주 www.acmicpc.net 문제 해결 과정 착안 기타줄의 패키지 가격과 낱개 가격을 각각 별도의 배열에 저장한 다음 오름차순으로 정렬하고, 패키지로 구매하는 경우와 낱개를 구매하는 경우를 비교하여 문제를 해결한다. 구현 필요한 기타줄의 수를 $N$이라 할 때, 다음과 같이 두 가지 조건을 비교하여 문제를 해결할 수 있다. 패키지로 구매하는 경우와 낱개로 6 개씩 구매하는 경우를 비교한다. 패키지로 구매하는 경우와 $N$.. 2023. 12. 26.
[Baekjoon] 1436번: 영화감독 숌 https://www.acmicpc.net/problem/1436 1436번: 영화감독 숌 666은 종말을 나타내는 수라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타워 www.acmicpc.net 문제 해결 과정 착안 $N$ 번째 종말의 수를 찾을 때까지 반복문을 통해 666부터 시작하여, 숫자를 문자열로 바꾸었을 때 666이라는 문자열을 포함하는지의 여부를 확인하여 카운팅하고 숫자를 1씩 증가시킨다(브루트 포스(brute-force) 방법). 또는, $N (1 \le N \le 10000)$ 번째 종말의 수가 가지는 규칙성을 파악하여 이를 활용해 문제를 해결한다. 구현 1) 숫자를 1씩.. 2023. 12. 22.
[Baekjoon] 1890번: 점프 https://www.acmicpc.net/problem/1890 1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net 문제 해결 과정 착안 가장 왼쪽 위의 칸에서 시작하여 이동할 때, 각 칸마다 오른쪽 또는 아래쪽으로 이동할 수 있는 두 가지의 경우가 있기 때문에 재귀를 통해 문제를 해결하면 문제에 따라 최대 지수 시간의 시간 복잡도($O(2^n)$)를 나타내게 될 수 있으므로, 이동할 수 있는 경우의 수를 누적하여 계산하는 동적계획법(dynamic programming)에 기반하여 문제를 해결하고자 .. 2023. 12. 21.
[Baekjoon] 1019번: 책 페이지 https://www.acmicpc.net/problem/1019 1019번: 책 페이지 첫째 줄에 0이 총 몇 번 나오는지, 1이 총 몇 번 나오는지, ..., 9가 총 몇 번 나오는지를 공백으로 구분해 출력한다. www.acmicpc.net 문제 해결 과정 착안 각 자릿수마다 숫자 0부터 9까지 등장하는 규칙성을 찾아 이를 이용해 계산한다. 책의 마지막 페이지가 5425 페이지라고 가정하여 아래와 같이 규칙성을 파악해보자. 위의 그림과 같이 1부터 5425까지 모든 숫자를 자릿수 별로 확인하기 편하게 나열해보면, 일의 자리가 0인 숫자: 0, 10, 20, $\cdots$, 5420 $\Rightarrow$ (543 - 1) 개 (첫 페이지가 1부터 시작하므로) 일의 자리가 1인 숫자: 1, 11, .. 2023. 12. 20.
[Baekjoon] 2629번: 양팔저울 https://www.acmicpc.net/problem/2629 2629번: 양팔저울 첫째 줄에는 추의 개수가 자연수로 주어진다. 추의 개수는 30 이하이다. 둘째 줄에는 추의 무게들이 자연수로 가벼운 것부터 차례로 주어진다. 같은 무게의 추가 여러 개 있을 수도 있다. 추의 무 www.acmicpc.net 문제 해결 과정 착안 추의 갯수가 $n$개일 때, 각각의 추를 사용하거나 사용하지 않고 무게를 만들 수 있는 경우의 수를 모두 계산하면 지수 시간($=O(2^n)$)의 시간 복잡도를 가지므로 동적계획법(dynamic programming)을 활용하여 문제를 해결하고자 하였다. 추가 하나씩 새로 주어질 때마다, 기존에 잴 수 있던 무게와 더불어 추가적으로 잴 수 있는 무게들은 다음과 같다. 새로 추가.. 2023. 12. 15.
[Baekjoon] 11967번: 불켜기 https://www.acmicpc.net/problem/11967 11967번: 불켜기 (1, 1)방에 있는 스위치로 (1, 2)방과 (1, 3)방의 불을 켤 수 있다. 그리고 (1, 3)으로 걸어가서 (2, 1)방의 불을 켤 수 있다. (2, 1)방에서는 다시 (2, 2)방의 불을 켤 수 있다. (2, 3)방은 어두워서 갈 수 없으 www.acmicpc.net 그래프 탐색 알고리즘과 관련한 문제는 자신 있다고 생각했는데, 문제에서 요구하는 것 잘못 파악 + 문제에 들어있는 함정 때문에 처음 작성했던 코드가 왜 틀렸는지 이해하느라 엄청난 시간을 소모해버렸당 문제 해결 과정 착안 시작 지점으로부터 방을 방문할 때마다, 방에 존재하는 모든 스위치를 켜면서 불이 켜진 방의 갯수를 증가시킨다. 이후 인접한 방.. 2023. 12. 14.

티스토리툴바