본문 바로가기
반응형

컴퓨터 사이언스/BOJ42

[c++] 백준 #10971 외판원 순회 2 이번 문제는 TSP(Travelling Salesman Problem)이라 하여 굉장히 익숙한 내용을 다루는 문제이다. 간단하게 내용을 요약해보자면, N개의 도시를 모두 다 방문하면서 처음 도시로 돌아가려고 할 때 가장 최소의 비용을 출력하는 문제이다. www.acmicpc.net/problem/10971 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 나는 dfs + 비트마스킹으로 문제를 풀었다. 맨처음 시작지점을 1~N까지 모두 돌아가면서 dfs를 돌리면 된다. .. 2021. 1. 24.
[c++] 백준 #1339 단어 수학 취미로 백준 다시 시작했다! 매우 깔끔한 논리로 풀 수 있는 문제였고, 오랜만에 푸는 문제였는데도 쉽게 감을 잡고 풀 수 있을 만큼 구현도 깔끔해서 오랜만의 포스팅으로 들고 왔다. www.acmicpc.net/problem/1339 각각의 알파벳 암호가 어떤 수를 가지고 있는 지 답에서 제시하지 않아도 되므로, 알파벳 정보를 일일이 따지지 않고도 그리디하게 풀기로 했다. 처음 봤을 때는 자리수가 높은 순서대로 알파벳을 맵핑시킨 후 더해주면 된다는 생각이 들지만, 그보다 낮은 자리수의 알파벳이 무엇인지에 따라 답이 바뀔 수 있기 때문에 이를 고려해주는 것이 필요하다. 예를 들면, 2 BC ACC 이렇게 두 수가 있을 때, 두번째 자리수에서 B와 C가 있는데 C의 갯수가 B보다 많기 때문에 A를.. 2021. 1. 15.
[c++] 백준 #16490 외계인의 침투 나는 이런 문제 푸는 걸 좋아한다. 물론 기하학을 잘하진 않는다. A를 (0, 0)으로 두자. 우리는 선분AB의 길이(t)를 알고 있으므로 이를 통해 외접원의 반지름을 구할 수 있다. 왜냐하면 삼각형이 정삼각형이므로 정삼각형의 무게중심과 원의 중심이 같기 때문이다. 이를 통해 원의 방정식을 세울 수 있고, 선분 AP의 길이 a를 알고 있으므로 두 식을 연립하면 P의 좌표를 구할 수 있다. B와 C는 정삼각형의 꼭짓점이므로 좌표를 쉽게 구할 수 있고 이를 통해 그냥 수학 식을 코딩으로 변환만 해주면 된다. - 다른 풀이 방법 점 P는 항상 점 B와 점 C 사이에 있을 것이므로 이분탐색을 하면서 점 P의 좌표를 구해도 된다고 한다. #include using namespace .. 2019. 11. 5.
[c++] 백준 #5000 빵정렬 정렬을 할 때마다 규칙성을 찾아야 하는 게 문제인데 나는 그걸 못 찾아서 친구의 풀이를 듣고 깨달음을 얻었다. 정렬을 할 때마다 역순 pair의 홀짝성이 유지가 된다는 것이 특징. 예를 들어 (4, 3, 2)는 (4, 3), (3, 2), (4, 2) 총 3개의 역순 pair를 가진다. 이를 빵정렬하면 (2, 4, 3)이 되는데 이거는 역순 pair를 (4, 3) 하나만 가진다. 그러면 역순 pair의 수가 홀수인 순열은 아무리 빵정렬을 해도 역순 pair의 수가 홀수개이다. 역순 pair 수가 짝수개가 죽어도 될 수 없다는 의미. 그러므로 주어진 두 input의 역순 pair 수를 세보고 둘다 짝수거나 둘다 홀수면 Possible, 아니면 Impossible을 띄우면 된다. 역순 pair를.. 2019. 11. 5.
반응형

티스토리툴바