[BOJ] 백준 1912 연속합 (Swift)
문제 https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 풀이 연속된 수들을 선택해서 가장 큰 수를 구하는 문제입니다. 그렇다면 이 두가지로 나뉠 것입니다. 연속해서 자기 자신까지 선택한 경우가 더 큰 경우 자기 자신만 선택한 경우 다이나믹 프로그래밍을 사용해서 풀 수 있습니다. [2, 1, -4, 3, 4, -4, 6, 5, -5, 1] 수열이 주어졌을 때를 확인해 봅시다. 첫번째 수를 확인해봅시다. 2를 선택하는 것이 가장 큰 합일 것입니다. 두번째 수를..
[BOJ] 백준 14889 스타트와 링크 (Swift)
문제 풀이 먼저, 스타트팀와 링크팀을 나누어 주어야 합니다. 스타트팀의 팀원들을 n / 2명을 뽑는다면, 자동으로 링크팀도 팀이 꾸려지게 됩니다. 저는 백트래킹을 사용해서 조합할 수 있는 팀을 구했습니다. 이제 팀이 나누어졌다면, 팀별로 능력치를 구해줬습니다. 1, 2, 3번이 팀이라면, $S_{12}, S_{21}, S_{13}, S_{31}, S_{23}, S_{32}$의 능력치가 팀의 능력치 일 것입니다. 반복문을 사용해서 구해주었고, 팀간의 능력치의 차이의 최소값을 구해주면 끝 입니다. 소스코드 후기 백트래킹을 사용해서 팀을 나눌 수 있었습니다. 팀을 나누었다면, 팀간의 능력치의 차이의 최소값만 구해주면 되는 문제였습니다.
