와드의 블로그

문제매우 큰 도화지에 자를 대고 선을 그으려고 합니다. 선을 그을 때에는 이미 선이 있는 위치에 겹쳐서 그릴 수도 있는데, 여러 번 그은 곳과 한 번 그은 곳의 차이를 구별할 수 없습니다. 이와 같이 선을 그었을 때, 그려진 선(들)의 총 길이를 구하는 프로그램을 작성하는 문제입니다.입력: 첫째 줄에 선을 그은 횟수 N (1 ≤ N ≤ 1,000,000)이 주어집니다. 둘째 줄부터 N개의 줄에 선을 그을 때 선택한 두 점의 위치 x, y (-1,000,000,000 ≤ x 출력: 첫째 줄에 그은 선의 총 길이를 출력합니다.링크: https://www.acmicpc.net/problem/2170풀이: 정렬 및 라인 스위핑 (Line Sweeping)주어진 선분들을 정렬한 뒤, 시작점부터 끝점까지 한 번에 ..

문제N개의 수로 이루어진 수열과 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자(+, -, ×, ÷)가 주어집니다. 주어진 수의 순서를 바꾸지 않고 연산자를 모두 끼워넣어 만들 수 있는 식의 결과 중, 최댓값과 최솟값을 구하는 프로그램을 작성하는 문제입니다.입력: 첫째 줄에 수의 개수 N (2 ≤ N ≤ 11)이 주어집니다. 둘째 줄에는 A1, A2, ..., AN이 주어집니다. 셋째 줄에는 합이 N-1인 4개의 정수(덧셈, 뺄셈, 곱셈, 나눗셈의 개수)가 차례로 주어집니다.출력: 첫째 줄에 만들 수 있는 식의 결과의 최댓값을, 둘째 줄에는 최솟값을 출력합니다.링크: https://www.acmicpc.net/problem/14888풀이: 백트래킹List와 같은 자료구조에 연산자를 모아두었다가 마지..

문제축구를 하기 위해 모인 N명(짝수)을 N/2명씩 스타트 팀과 링크 팀으로 나누려고 합니다. 사람마다 다른 사람과 같은 팀이 되었을 때 더해지는 능력치 S[i][j]가 주어집니다. 스타트 팀의 능력치와 링크 팀의 능력치의 차이를 최소로 하는 프로그램을 작성하는 문제입니다.입력: 첫째 줄에 N (4 ≤ N ≤ 20, N은 짝수)이 주어집니다. 둘째 줄부터 N개의 줄에 능력치 배열 S가 주어집니다.출력: 첫째 줄에 스타트 팀과 링크 팀의 능력치 차이의 최솟값을 출력합니다.링크: https://www.acmicpc.net/problem/14889풀이 1: HashSet을 활용한 백트래킹Set를 사용하여 스타트 팀에 속할 인원을 선택하는 완전탐색 풀이입니다.팀원 선택: go 함수에서 반복문을 통해 idx부터 ..