삼성 역량테스트 문제 (13) 썸네일형 리스트형 백준 15686 <치킨 배달> 이 문제도 마찬가지로 조합을 구할 수 있냐 하는 문제인 것 같다. 치킨집이 최대 13개이기때문에 최대 13 C m 이 될 것이고 이 값은 1만이 넘지 않는다. 집의 개수는 최대 2 * N 개가 넘지 않으니 최대 100개 이므로 집에서 치킨집까지의 모든 거리를 계산해도 천만? 정도가 될 것이다. 이 문제는 이전 문제와 다르게 접근을 해보았는데 visit배열을 이용해서 방문을 체크해주고 방문한 경우에는 num+1을 해서 재귀를 해주도록 하였다. 이 문제에서 주의해야 할 점은 최대 M개를 고르는 문제라고 하여 그 이하의 경우도 생각해주어야 하는가? 였다. 답은 당연히 No!이다. 우리가 구하는 것은 집에서 가장 가까운 치킨집을 고르는 것이기 때문에 치킨집의 개수는 많을수록 좋다. 그다음은 각각의 집에 대해 가.. 백준 14889 <스타트와 링크> 일반적인 조합 문제이다 최대 20 C 10 이기 때문에 184756번이고 10명의 팀원을 각각 값을 계산해도 100이므로 184765*10 하고 두 팀이니 x2 해서 400만이 되지 않기 때문에 시간 내에 무사히 통과할 수 있는 문제이다. 삼성 A형 테스트 치고는 접근하는 방향도 생각하기도 쉬웠던 문제이다. 20명의 사람 중 절반을 나누는 조합이 부분이다. find 함수에서는 a팀에 속하지 않은 사람들을 b의 배열에 넣고 각각의 사람들을 기준으로 팀의 능력치를 구하고 난 뒤 두 점수의 최소 차이를 구한다. visit 함수를 이용해서 a팀에 속해있는 인원을 1로 만들어주고 차후에 a팀을 제외한 인원을 b팀에 넣어준 코드이다. 그 후에는 간단하게 각팀의 능력치를 계산해줘서 최소를 대입해주면 끝나는 간단한 문.. 백준 14502 <연구소> 이 문제 또한 완전탐색의 가장 기본적인 문제라고 볼 수 있다. 가장 기본적인 틀로는 0이 있는 자리를 3가지만 뽑는 조합으로 구한 다음 DFS 또는 BFS를 통해 바이러스를 퍼트린 다음 빈칸을 세어주는 문제로 간단하게 풀 수 있다 . 예전에는 다른 방법을 찾아보고 그랬었는데 가장 먼저 이런 문제를 완전탐색으로 접근하고 시간복잡도를 계산한 다음 가능하다면 완전탐색으로 문제를 해결하도록 성장하였다. 이 문제를 완전 탐색으로 푼다면 전체가 0이라고 해도 조합을 계산해본다면 최대크기가 8*8 64이기때문에 3개를 뽑는다고 해도 64C3 이기때문에 41664번이 수행될것이고 완전탐색을 그 후에 한다고 해도 2666496으로 300만이 넘지 않는다. 그러므로 완전탐색으로 접근이 가능한 문제인 것이다. 우선적으로 값.. 이전 1 2 다음
