본문 바로가기
반응형

전체 글

1963번 1963번 - 소수 경로 문제를 보는 순간 '소수' -> 2가지 방법 ( 1. 에라토스테네스의 채. 2.루트N까지 for문으로 나눠보기) 그리고 숫자들을 정점이라고 했을 때, 변할 때 가중치가 따로 없으므로 1이라고 한다면 최단 거리를 구하기 떄문에 BFS로 풀 수 있다. 그래서 처음에 에라토스테네스의 채를 이용해서 N의 범위인 9999까지 소수를 모두 구해놓는다. 그리고 시작점을 BFS의 시작점으로 놓고, 각 자리의 수를 변화시킨다. 그때 변화된 점이 방문한 적이 없고, 소수이면 큐에 집어 넣는다. 목표로 하는 값이 나오면 while 문을 나오고 dist값을 반환해준다. 단, 내가 처음에 빠졌던 함정은 네자리 숫자이기 때문에 맨 앞에만 0이 올 수 없다는 점. 12345678910111213141516.. 더보기
10971번 10971번 - 외판원 순회2 유명한 TSP(traveling salesman problem) 인 외판원 순회다. 이 문제는 N 제한이 작기 때문에 (N 더보기
next_permutation 함수 사용법 http://alhena.tistory.com/43 감사합니다. 더보기
10819번 10819번 - 차이를 최대로 이 문제는 N 제한이 작기 때문에 완전탐색을 통해서 충분히 풀 수 있다. 예전에는 강의를 보고 next_permutation 으로 풀었으나, next_permutation 함수에 대한 이해가 부족해서 스스로 재귀를 통해 permutation 을 구현해서 풀어보았다. 인덱스 값을 재귀함수를 통해서 변화시켜준다. 이때, used 함수를 이용한다. 그 뒤 구한 permutation 이 N 과 일치하면 cal 함수를 통해서 최대값을 구한다. next_permutation 함수는 정렬한 뒤에 이용해야한다. 이유는 http://alhena.tistory.com/43 에서 잘 설명해주신다. 123456789101112131415161718192021222324252627282930313.. 더보기
1451번 1451번 - 직사각형으로 나누기 일단 총 여섯가지 케이스가 발생하게 된다. 그 중에서 나는 번호 매긴 것 처럼 1번과 2번은 getSumM1, getSumN1 으로 풀었다. 그리고 3,4,5,6번과 같은 경우는 선을 그은 것처럼 직사각형을 4분할 하였다.(getSum 함수) 그리고 각각 직사각형의 합을 구하였다. sum[0]~sum[3] 까지 그래서 왼쪽 상단을 0사분면, 오른쪽 상단을 1사분면, 왼쪽 하단을 2사분면, 오른쪽 하단을 3사분면이라고 한다면, 위의 3,4,5,6번 그림을 나타낼 수 있다. 그래서 이를 통해서 최대값을 구해내는 방식으로 문제를 풀었다. ##문제점## 처음에는 1번,2번 그림을 N이 1일때, M이 1일때만 가능한 그림이라고 생각하여 실수를 저질렀다. 직사각형 네개로 모든 것을.. 더보기
1107번 1107번 - 리모컨 처음에 어떻게 풀어야할까 고민을 많이 했다. 완전 탐색이란 걸 알았는데도, 어떤 식으로 구현할지 몰랐다. 그러다가 일단, 두가지 케이스로 생각했다. 첫번째, +와 - 만을 이용해서 움직이는 경우.두번째, 특정숫자로 간 후, +와-만을 이용해서 움직이는 경우. 하지만 특정 숫자로 어떻게 가야할지에 대해서 감이 잡히지가 않았다. 그러던 중 내가 숫자로 가기 보다는 그 목적 숫자를 +1, -1 하면서 갈 수 있는 가장 빠른 경우 ( 그래야 특정 숫자로 이동 후, +와 - 연산을 최소화 할 수 있다.) 를 찾고 그 이후에 그 숫자의 자릿수를 더해주면 된다고 생각했다. x는 목적지 기준으로 - 를 해주고, y는 목적지를 기준으로 +를 해주면서 가장 가까운 값을 찾았다. 만약 리모컨의 모든 숫.. 더보기
1476번 1476번 - 날짜 계산 완전 탐색 1234567891011121314151617181920212223242526272829303132#include using namespace std; int main(){ int E, S, M; cin >> E >> S >> M; int e = 1, s = 1, m = 1; int year = 1; while (e != E || s != S || m != M) { e++, s++, m++, year++; if (e == 16) { e = 1; } if (s == 29) { s = 1; } if (m == 20) { m = 1; } } cout 더보기
11399번 11399번 - ATM 그리디 알고리즘으로 줄을 어떻게 세울지 결정하는 문제이다. 시간이 가장 적게 걸리는 순으로 짜면 된다. i 번째 사람이 걸리는 시간을 T[i] 라고 하면 T[1]=P[1]T[2]=P[1]+P[2]T[3]=P[1]+P[2]+P[3].....T[i]=P[1]+P[2]+P[3]+....+P[i] 가 된다. 그래서 T 의 전체 합이 최소로 만들기 위해서는 가장 많이 중복되는 수가 가장 적은 수가 되어야 한다. 그래서 그냥 sort를 통해 오름차순으로 정렬하고 합을 구했다. 증명) 시간이 가장 적게 걸리는 사람 순이 아닌 최적의 답이 있다고 가정해보자. 그게 A B C 라고 해보자. 그리고 시간이 가장 적게 걸리는 사람 순으로 세운 답이 B C A 라고 해보자. 그러면 B N; for (i.. 더보기
반응형

티스토리툴바