문제 풀이/백준 (BOJ)

[백준/BOJ] 14889번: 스타트와 링크 (백트래킹 기법) - C++ 문제풀이

문제 설명 문제 링크: https://www.acmicpc.net/problem/14889 풀이한 그룹의 사람들 중에서 스타크와 링크 팀으로 나누어 각 팀의 능력치 차이의 최소 값을 출력하는 문제입니다. 짝수인 N 사람들 중에서 M=N/2 사람을 뽑아 팀을 만드는 것부터 해야겠네요.편의상 팀명을 A팀이라고 하겠습니다.주의할 점은 1번과 3번을 뽑는 것과 3번과 1번을 뽑는 것은 같은 것으로 봐야 한다는 거죠.이 경우의 수를 제거하기 위해서, 다음 사람의 번호는 이전 사람의 번호보다 크도록 뽑았습니다.void Pickup( int num, int start){ if ( num == M){ return; // 팀에 필요한 사람을 뽑았음 } int to = N - M + num; ..

2024. 5. 15.

문제 풀이/백준 (BOJ)

[백준/BOJ] 15649번, 15651번: N과 M (백트래킹 기법) - C++ 문제 풀이

문제 설명 문제 링크: https://www.acmicpc.net/problem/15649 풀이이 문제는 1부터 N까지의 수를 가지고 M 길이의 수열을 만들어 출력하는 문제입니다.그런데, 같은 수를 사용해서 수열을 만들 수 없습니다. 15651번 문제는 위 문제와 같은 데, 차이점은 같은 수를 사용해서 수열을 만들 수 있다는 점이 다를 뿐입니다.우선 이 문제를 푼 후, 이를 확장해서 15651번 문제를 해결하겠습니다. 이 문제는 커다란 자루에 N개의 공을 넣고, 한 개씩 뽑아 나열하는 것과 같습니다.그럼 어떻게 뽑아야 모든 경우의 수열을 만들 수 있을까요? 예를 들어, N = 8, M = 2라고 해보죠. 1. 첫 번째 공을 뽑습니다.   공에 있는 숫자를 기록하고, 자루에서 뺍니다. 2. 두 번째 공을 ..

2024. 5. 11.

문제 풀이/백준 (BOJ)

[백준/BOJ] 9663번: N-Queen (백트래킹 기법) - C++ 문제 풀이

문제 설명 문제 링크: https://www.acmicpc.net/problem/9663  풀이체스에서 퀸은 거리와 상관없이 직선, 대각선에 있는 적을 공격할 수 있는 말입니다.이런 N개의 퀸을 N x N 크기의 체스판에 서로 공격할 수 없도록 배치할 수 있는 방법의 수를 찾는 문제입니다.  위의 이미지는 4x4 체스판 위에 4개의 퀸들이 서로 공격할 수 없도록 배치된 예를 보여주고 있습니다.이 문제는 백트래킹 기법의 전형적인 문제입니다. 백트리킹 기법이란 트리구조 문제의 정답을 찾는 과정에서, 더 이상 진행할 수 없는 노드에 도달하게 되면 이전 노드로 되돌아가 다른 방향으로 정답을 탐색하는 방법을 말합니다.   위의 이미지를 대상으로 탐색 과정을 설명하면,1번 노드부터 시작해서 2번 노드에 도달하여 정..

2024. 5. 11.