BOJ
-
BOJ 14169 Lasers and MirrorsBOJ 2019. 7. 10. 22:05
좌표압축 후 x,y 각각에 대해 좌표값을 넣어 인접리스트를 만든 후 BFS를 실행해주었다. (x좌표 기준 y축과 평행한 직선을 긋고, 그와 만나는 지점들을 리스트로 저장, y축 기준도 마찬가지) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 1..
-
BOJ 12011 Splitting the FieldBOJ 2019. 7. 10. 21:23
점들을 두 사각형으로 재분할하는 문제이다. 사각형을 이루는 선은 항상 x축이나 y축과 평행하다는 조건이 있다. 이 조건으로부터 만들어지는 두 직사각형은 두 축 중 하나와 평행하는 임의의 직선을 기준으로 항상 양쪽에 위치한다는 것을 알 수 있다. 양쪽부터 분할선까지의 점들을 순차적으로 탐색하면서 분할선이 y축과 평행할 경우에는 y좌표의 최대, 최소를, x축과 평행할 경우에는 x좌표의 최대 최소를 저장해주면 분할된 두 직사각형의 넓이를 쉽게 알아낼 수 있다. 각각의 최대 최소를 세그먼트 트리로 저장하는 방법으로 해결할 수도 있다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 3..
-
BOJ 16637 괄호 추가하기BOJ 2019. 3. 2. 00:52
주어진 수식에서 임의의 위치에 괄호를 추가하였을 때 계산되는 최댓값을 찾는 문제이다. 모든 경우를 다 따져줘야 하는데, 재귀함수를 만들어 식을 차례로 읽어가는 방식으로 해결했다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879#include #include #include using namespace std; typedef long long ll; ll n, maxn = LLONG_MIN, num1[20], num2[20];char arr[20]; // 더하기ll Add(ll a, ll ..
-
BOJ 5214 환승BOJ 2019. 2. 26. 00:04
모든 역 각각의 관계를 그래프로 구성한다면 너무 많은 메모리와 시간이 소모된다. 따라서 각 동일한 튜브에 속했다는 조건을 적절히 사용해주었다. 발코딩이다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869#include #include #include using namespace std;// disc[] = 각 역(노드)의 방문 여부// tube_chk[] = 각 튜브의 방문 여부int n, k, m, disc[100100], tube_chk[1010];// tube_list[] = 노드가 속한 하이퍼튜브의 리스트// tub..
-
BOJ 16920 확장 게임BOJ 2019. 2. 25. 16:33
S[i]의 최댓값이 10^9 임에 주의하지 않으면 시간초과가 발생한다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889#include #include using namespace std; // s[] = 각 플레이어의 횟수// res[] = 답int n, m, p, s[10], res[10], map[1010][1010], tot; int dx[] = { 0,0,1,-1 };int dy[] = { 1,-1,0,0 }; // 확장 순서를 담아두기 위한 큐..
-
BOJ 2573 빙산BOJ 2018. 11. 17. 19:04
N과 M이 최대 300까지 가능하기 때문에, 이차원 배열의 크기는 최대 90000이다. 매번 배열의 모든 값을 탐색해주는 방식이라면, 최악의 경우 연산이 1억번이 넘어 1초의 제한시간이 부족할 수 있다.(뇌피셜임) 빙산의 개수가 최대 10000개이므로 빙산의 위치만 따로 관리해준다면 조금 더 빠른 시간에 문제를 해결할 수 있다. 빙산의 높이가 0이 된다면 인접한 빙산의 높이 변화에 영향을 줄 수 있기 때문에, 높이 변화를 temp라는 배열에 저장해준 이후에 빙산의 높이를 갱신해주는 방식으로 해결했다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162..