Hello World!

문제 링크: 백준/BOJ https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 처음 bfs에 입문했을 때 풀었던 문제다. 상차가 h층만큼 존재하기 때문에 1층만 있는 문제와 다른점은 한 지점에서 이동할 수 있는 방향이다. 2차원에서와 다르게 위, 아래로도 이동할 수 있으므로 총 6가지 방향에 대한 배열을 선언해주었다. 개인적으로 tuple을 사용하면 값에 대한 접근 방식이 귀찮아서 구조체를 더 애용하는 편이다. /* 20200..

문제 링크: 백준/BOJ https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 아주 아주 유명한 dp 문제다. dp[$k_j$] = 가치의 합이 $k_j$원이 되게 하는 경우의 수 즉, dp[5]의 경우 5원을 만들 수 있는 경우의 수를 저장한다. 이 문제를 풀기 위한 점화식은 dp[$k_j$] = dp[$k_j$] + dp[$k_j$ - coin[i]] 이때 주의할 점은 초기값 dp[0]을 설정해줘야 함이다. 그 값을 뭘로 설정해줘야 할지는 조금만 ..

문제 링크: 백준/BOJ https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net LIS 문제였다. LIS에 대한 자세한 설명은 아래 글에 있다. https://hellooworld.tistory.com/21 [BOJ] 11053번: 가장 긴 증가하는 부분 수열 문제 링크: 백준/BOJ https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프..

문제 링크: 백준/BOJ https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. www.acmicpc.net 아주 전형적인 LIS 문제였다. LIS는 Longest Increasing Subsequence의 준말로, 주어진 수열에서 오름차순으로 정렬된 가장 긴 부분 수열을 찾는 문제이다. 부분 수열은 연속적일 필요가 없다는 것을 명심하자. 만약, 부분 문자열(substring)이었다..

문제 링크: 백준/BOJ https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 백트래킹에 거의 정형화되어 있는 재귀 함수를 짜는 연습하기에 좋은 문제였다. 단, 문제에서 암호를 사전 순으로 출력하라 했으므로 재귀 함수를 호출하기 전에 문자들을 정렬해주었다. /* 20200401 baekjoon 1759번 암호 만들기 */ #include #include using namespace std; char arr[15]; char ans[15]; bool isC..

문제 링크: 백준/BOJ https://www.acmicpc.net/problem/1748 1748번: 수 이어 쓰기 1 첫째 줄에 N(1≤N≤100,000,000)이 주어진다. www.acmicpc.net 입력받은 N에 대해 자릿수를 계산한 뒤 해당 자릿수를 제외한 자릿수를 가지는 수의 개수를 arr배열에 미리 저장해둔 값을 이용해 계산해주었다. 그리고 해당 자릿수의 값들은 개수를 직접 계산해서 더해주었다. 예시로 N = 12인 경우를 간단히 살펴보자. 12는 두 자릿수이므로 len = 2이다. 한 자릿수의 수들(1~9)는 arr [1] 개이고 각 수는 한 자릿수이므로 총 9자리이다. 두 자릿수는 12 - 10 + 1 = 3개이고, 각 수는 두 자릿수이므로 총 3*2 = 6자리이다. 따라서 총 15자리..