본문 바로가기
반응형

알고리즘/SW EXPERT

3349. 최솟값으로 이동하기 3349. 최솟값으로 이동하기 처음에는 BFS를 삼차원배열로 풀었더니 런타임에러... 그래서 생각해보니, 그냥 좌표값만을 가지고 충분히 거리를 구할 수 있었다. (x1,y1)->(x2,y2) 로 이동한다고 했을 때 , (x2-x1)*(y2-y1) 이 양수라면, 이는 북동 혹은 남서로 이동하므로, 지름길을 사용할 수 있게 된다. 따라서 그런 경우에 따라서 나누면, 좌표값만을 가지고 충분히 거리를 구할 수 있게 된다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051#include#include#include using namespace std; int main(){ int tc; cin >.. 더보기
3499. 퍼펙트 셔플 3499. 퍼펙트 셔플 단순히 카드를 섞는 문제, 카드를 반으로 나눠서 섞어서 출력하면 된다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667#include#include#include#includeusing namespace std; void init(){ }int main(){ ios::sync_with_stdio(false); cin.tie(NULL); int tc; cin >> tc; for (int t = 1; t > n; vector d1; vector d2; if (n % 2 == 1) { half = n / 2 + .. 더보기
3752. Digit sum 3752. Digit sum 쉬운 문제여서 재귀함수로 구현해 보았다. 1234567891011121314151617181920212223242526272829303132333435363738394041#include using namespace std; long long go(long long n){ long long ret = 0; long long sum = 0; while (n !=0) { sum += n % 10; n /= 10; } if (sum >= 10) { ret += go(sum); return ret; } else { return sum; } }int main(){ int tc; cin >> tc; for (int t = 1; t > n; cout 더보기
3752. 가능한 시험 점수 3752. 가능한 시험 점수 다른 분이 힌트를 주셔서 풀게 됐는데, 이런 방식의 문제를 어렴풋 본 것 같다. 처음에 DP라고 생각했지만, DP로 풀기에는 뭔가 이상하다 했는데, 쉬운 풀이 방법이 존재했다. 가능한 점수 범위가 10000까지기 때문에, 배열을 10000개 선언한다. 그리고 0 을 true 로 체크하고 시작한다, 예를 들어 2, 3, 5점이라는 배점을 가지고 있을 때, 처음에 0 을 true 로 체크 그 다음에 배점은 2 이기 때문에 0 , 0+2 를 true 로 체크 다시 for문을 돌면서 배점이 3이기 때문에 0, 0+3, 0+2+3, 을 true 로 체크... 이런식으로 중복되는 값들을 간단하게 처리 할 수 있게 된다. 참으로 똑똑하고 쉬운 방법인거 같다. 1234567891011121.. 더보기
3143. 가장 빠른 문자열 타이핑 3143. 가장 빠른 문자열 타이핑 이 문제는 원래 단어 한개씩 치다가, 치트키가 있는 경우 여러단어를 한꺼번에 칠 수 있다. 그리고 최솟값을 구해야 하기 때문에, 최단거리 그래프 문제로 보고 다익스트라 알고리즘을 사용했다. 단순히 BFS로 구현해도 될 것 같다. 그래서 매번 현재 위치에서 + 1 을 하거나, 치트키가 가능한 경우는 가능한 만큼 넘어가면 된다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172#include#include#includeusing namespace std;const int INF = .. 더보기
1494. 사랑의 카운슬러 1494. 사랑의 카운슬러 개인적으로는 뭔가 이상한 문제라고 생각한다. 벡터를 구하는 방법에 대한 설명이 좀 더 필요한 문제라고 생각한다. 예를들어 A(6,0) B(3,3), C(-7,2), D(-4, -1) 이라 할때, 문제에서는 AB(3,-3) , CD(-3,3) 이고 두 벡터의 합은 (0,0) 이므로 답 0 이렇게 나오지만, AB(3,-3),DC(3,-3) 이라고 구하면 두 벡터의 합은 (6,-6) 이므로 답이 72가 되기 때문이다. 내가 이상한 해석을 하는건지는 모르겠지만 저런경우에 대한 명확한게 떨어지는 것 같다 아무튼 결국 출제자가 원하는 바는, 결국 벡터의 합의 제곱을 구하기 때문에 모든 쌍을 구하는 게 아니라는 점이다. 즉, 움직이는 절반의 지렁이만 정하고, 움직이는 지렁이와 움직이지 않는.. 더보기
1808. 지희의 고장난 계산기 1808. 지희의 고장난 계산기 처음에 BFS로 풀려했지만, 뭔가 실마리가 보이지 않아 그냥 완전탐색을 했다. 근데 완전탐색도 어떤식으로 할까 고민하다가, 계산기에 곱하기 밖에 없다는 점을 알고 문제를 풀었다. 곱하기이기 때문에, 주어진 N의 약수들을 모두 구했다. 그리고 그 약수들 중에서 주어진 값으로 만들 수 있는 것만 canmake 벡터에 담아주었다, 그 길이와 함께. 그리고 canmake 안의 값들을 재귀로 모든 값을 구하도록 하였다. 수를 만드는 과정에서 int 변수를 넘어가서, 오류 나는게 있어서 long long 타입으로 바꿔주었고, 가지치기를 위해서 큰수부터 하면서, 이전 값을 저장해서 계속해서 큰수가 만들어지지 않도록 pre 라는 변수를 넘기면서 재귀를 구현했다. 또 0과 1일때는 따로 .. 더보기
반응형

티스토리툴바