공부하자

https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 문제 정리 팀의 능력치 : 팀에 속한 모든 쌍의 능력치 Sij의 합 = Sij + Sji 두 팀의 능력치 차이의 최솟값을 구하기 생각 모든 경우의 수를 구해야 하긴 하는데… 1. 팀 구성 방식 - 중복이 허용되지 않으니까 순열로 구해야 하긴 함! 한 팀에 속하면 visited로 방문 표시를 하면서 방문한 팀이 n/2될 때 까지 방문하고! 이런 식 2. 팀의 능력치 비교 - 표에서 그대로 가져오는데 두 팀의 능력치 차를..

https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 문제 정리 주어진 도시 정보에서 M개의 치킨집만 남기는데 치킨집과 집 사이의 총 거리가 가장 적게 되도록 M개를 골라서 도시의 치킨 거리의 최솟값을 구하면 됨! (각 집과 치킨집 사이의 거리의 총 합이 최소가 되는) 생각 브루트포스로 모든 M개를 골랐을 때마다 거리를 다 구해놓고 그 중 min을 구함! 근데 M개를 고르는 로직은 어떻게 하지? 모든 경우의 수를 구한다고 하면 ..

https://www.acmicpc.net/problem/3085 3085번: 사탕 게임 예제 3의 경우 4번 행의 Y와 C를 바꾸면 사탕 네 개를 먹을 수 있다. www.acmicpc.net 문제 정리 문자가 들어있는 보드 값이 주어지면 위치를 서로 바꿔 같은 행이나 열을 만들면 사탕을 먹을 수 있다. 먹을 수 있는 최대 사탕의 개수를 구하는 문제 생각 음... 근데 이동만 하면 3의 배수로 사탕이 없어지는 거 아닌가? 아닌가 문제 이해를 잘못했나... -> 먹으면 그 다음은 이동을 못하나봐 문제 이해!!!! 그냥 딱 한 번만 바꿨을 때 최대의 사탕을 구하면 된다! 상하좌우 4방향을 전부 검사할 것인지, 두 방향만 고정해서 반복되는 경우를 줄일 것인지 선택을 해야된다 그냥 중복되는 경우를 줄이기 위해 ..

https://www.acmicpc.net/problem/2798 2798번: 블랙잭 첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다. 합이 M을 넘지 않는 카드 3장 www.acmicpc.net 알고리즘 스터디 하는 친구가 가져온 문제가 백트래킹 문제들인데 브루트 포스 개념조차 기억이 안 나서... ㅠㅠ 개념 리마인드 겸 브루트 포스 문제의 대명사인 블랙잭 문제를 다시 풀어보고자 한다 브루트 포스의 종류 순차 탐색 - 선형 구조를 순차적으로 탐색 DFS(깊이 우선 탐색) - 비선형구조를 점점 더 깊게 깊이를 우선적으로 탐색하는 방법 BFS(너비 우선 탐색)..

https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 퀸이 서로 공격할 수 없게 놓는 방법 : 같은 행 / 같은 열 / 같은 대각선 상에 위치하지 않아야 한다. (최지웅 교수님한테 배운 ㅎ) 생각 1. 백트래킹 문제니까 되추적 알고리즘을 쓴다 1.1. 상태 조건 트리를 어떻게 구성할 것인가? -> 트리까지 그릴 필요는 없는 문제인듯 아닌가 하하 1.2. promising 조건을 뭘로 할 것인가? -> 행 / 열 / 대각선이 겹치는지 확인하기 1차원 배열을 써도 되는..

https://www.acmicpc.net/problem/2231 2231번: 분해합 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 www.acmicpc.net 생각 1. 1부터 커지면서 분해합 비교 (최대 N까지 비교) 2. 하나하나 분해하는 방법을 어떻게 구현 할 것인가??? 2.1. N을 string으로 변환하여 하나씩 받아오기... 미친짓이다 2.2. 10으로 나눠서 자리수 나누기!!! 아는 거 쓰자! //i는 for문으로 1부터 커지도록 함 while(i != 0){ sum += i % 10; i /= 10; } 정답..

https://www.acmicpc.net/problem/7568 7568번: 덩치 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시된다. 두 사람 A 와 B의 덩 www.acmicpc.net #include #include #include using namespace std; int main(){ int N, num1, num2; cin >> N; int arr[N] = {0}; vector v; //입력 for(int i = 0 ; i> num1 >> num2; v.push_back(pair (num1, num2)); } for(int i = 0 ; i

https://www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 와 문제 이해를 못해서 하루종일 헤맨 문제... 그냥 어지간히 안풀린다 싶으면 문제 이해를 위해서라도 검색을 해보자 ㅎ 생각 1. 비교를 할 WB / BW 체스판을 미리 만들어 두고 비교를 하자 2. 여기서 키포인트는 한 번만 비교를 하는게 아니라 움직여가면서 비교를 하는 것! #include #include using namespace std; string WB[8] = { "WBWBWB..