[BOJ] 백준 2565 전깃줄 (Swift)
문제 https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 풀이 전깃줄이 교체하는지 어떻게 알 수 있을까요? (1, 5), (2, 4)를 보시면 교차하고 있는 형태입니다. (1, 3), (2, 4)은 어떨까요? 두 전깃줄이 교차하고 있지 않습니다. (a1, b1), (a2, b2) 일 때, a1 b2 인 경우 교차한다고 할 수 있습니다. 연결되어 있는 위치를 입력받은 후, a를 기준으로 오름차순으로 정렬해준다면 b만 확인해도 교차하는..
[BOJ] 백준 11054 가장 긴 바이토닉 부분 수열 (Swift)
문제 https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 풀이 이 문제는 가장 긴 증가하는 부분 수열 문제를 응용하는 문제입니다. https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 3..
[BOJ] 백준 11053 가장 긴 증가하는 부분 수열 (Swift)
문제 https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 풀이 수열 A = {10, 20, 10, 30, 20, 50} 경우에 가장 긴 증가하는 부분 수열을 찾아봅시다. 첫번째 요소인 10만 봤을 때, 자기 자신도 수열이기 때문에 길이는 1입니다. 두번째 요소에서 이전 요소들을 확인해봅시다. 10 보다 20이 크기 때문에 (10의 길이 + 1)이 증가하는 부분 수열의 길..
[BOJ] 백준 2156 포도주 시식 (Swift)
문제 https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 풀이 계단 오르기 문제와 비슷한 문제였습니다. 하지만 계단 오르기와 다르게, 마지막 포도주를 꼭 먹어야 하지는 않습니다. [1, 99, 100, 2] 와 같은 경우 99와 100을 먹는게 가장 큰 값입니다. 마지막 2를 먹을 필요가 없습니다. [100, 99, 1, 2, 100, 1] 로 포도주가 나열되어 있다고 가정합시다. 첫번째 포도주 까지 있다면, 첫번째 포도주를 마셔야 무조건 가장 많이..
[BOJ] 백준 10844 쉬운 계단 수 (Swift)
문제 https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 N이 1일 때는 1...9 까지의 수가 계단 수 입니다. N이 2일 때 앞의 자리가 1인 경우, 0 2 2인 경우, 1 3 3인 경우, 2 4 4인 경우, 3 5 .. 7인 경우, 6 8 8인 경우, 7 9 9인 경우, 8 N이 2일때, 끝나는 수가 0과 9가 아닌경우는 2번씩 등장하게 됩니다. 예를 들어 끝나는 수가 3인 경우, 앞의자리가 2일때와 4일때 2번 등장합니다. 정의 : $f(n, d)$ = 길이가 n, 마지막 자리의 수가 d인 계단수 구하는 답 : $f(n,0) + f(n,1) + ....
