Program Programming Programmer

문제: https://www.acmicpc.net/problem/1007 만약 (x1, y1), (x2, y2), (x3, y3), (x4, y4) 이란 점들이 있고 이 중(x1, y1), (x3, y3)을 선택하여 벡터를 만들고 (x2, y2), (x4, y4) 를 선택해 벡터를 만들었다고 할 때,첫 번째 벡터는 (x1 - x3, y1 - y3) 으로 표현할 수 있고 두 번째 벡터는 (x2 - x4, y2 - y4) 으로 표현할 수 있습니다.그리고 두 벡터의 합은(x1 + x2 - (x3 + x4) , y1 + y2 - (y3 + y4)) 이라 할 수 있습니다. 여기서 만약 x1 + x2 + x3 + x4 를 미리 구해두고벡터가 되는 점의 한 쪽들을 선택하며 그 점들의 x 좌표들을 구해둔다면즉 예에서는..

문제: https://www.acmicpc.net/problem/1006 처음에는 brute force 로 풀어봤으나 최대 N 의 값이 10000 이기 때문에 시간이 초과됩니다. 따라서 memoization 방법을 사용해야 되는데 그러기 위해서는 1번부터 N - 1 까지 순차적으로 우측 방향으로만 진행하며 경우의 수를 찾아야 됩니다. 이때 문제는 1번과 N + 1번에서 왼쪽으로 진행되는 방향은 고려되지 않는다는 점이 문제입니다. 해당 부분에 대해 한참 고민을 하다 사이트의 질문 검색을 통해 하드 코딩을 하는 방법으로 조언을 얻어 해결 했습니다. my solvingc++12345678910111213141516171819202122232425262728293031323334353637383940414243..

문제: https://www.acmicpc.net/problem/1005 처음에는 bruteForce 방법으로 풀었다가 시간 초과! 그래서 memoization 방법을 이용해 시간 복잡도를 줄여 풀었습니다. my solvingc++12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485#include #include #include #include #include #include using namespace std; multimap techTrees;vector buildin..

문제: https://www.acmicpc.net/problem/1004 start 와 goal 지점을 둘러싸고 있는 행성의 개수를 구하는 방법으로 풀었습니다. 단, start 와 goal 둘 다 둘러싸고 있는 행성은 제하였습니다. my solvingc++12345678910111213141516171819202122232425262728293031323334353637383940414243444546#include #include #include using namespace std; struct Pos{ int x, y, r;}; bool whetherAEncloseB(Pos a, Pos b){ return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y)..

문제: https://www.acmicpc.net/problem/1003 파보나치를 구할 수 있는 재귀함수에서 0 과 1인 경우가 불리는 횟수는 나열을 해보면0의 경우 주어진 n - 1 의 파보나치 수1의 경우 주어진 n 의 파보나치 수와 같다는 것을 알 수 있습니다.그리고 파보나치 수의 경우 n이 커지면 시간복잡도가 매우 커지기 때문에 memoization 을 사용해 시간 복잡도를 줄여 풀었습니다. my solvingc++1234567891011121314151617181920212223242526272829303132333435363738394041#include #include #include #include using namespace std; map cache;int fibonacci_dp(in..

문제: https://www.acmicpc.net/problem/1002 두 원 사이의 접점을 구하는 문제입니다. 해외 judge 사이트에 비해 어려웠던 점은 실패 시 어느 부분이 틀렸는지 정보를 제공해주지 않는다는 점입니다. 마지막으로 터렛안에 군인이 있을지는 생각 못했었네요 ㅋㅋ; my solvingc++12345678910111213141516171819202122232425262728293031323334353637383940414243444546#include #include #include #include using namespace std; struct Pos{ int x, y, r;}; int getNumIntersection(Pos a, Pos b){ double distance_cent..

To brighten up the gala dinner of the IOI'98 we have a set of N (10

Runaround numbers are integers with unique digits, none of which is zero (e.g., 81362) that also have an interesting property, exemplified by this demonstration:If you start at the left digit (8 in our number) and count that number of digits to the right (wrapping back to the first digit when no digits on the right are available), you'll end up at a new digit (a number which does not end up at a..

For many sets of consecutive integers from 1 through N (1

A certain book's prefaces are numbered in upper case Roman numerals. Traditional Roman numeral values use a single letter to represent a certain subset of decimal numbers. Here is the standard set: I 1 L 50 M 1000 V 5 C 100 X 10 D 500 As many as three of the same marks that represent 10n may be placed consecutively to form other numbers:III is 3CCC is 300Marks that have the value 5x10n are never..