본문 바로가기

분류 전체보기171

백준 1007 / C++ https://www.acmicpc.net/problem/1007 1007번: 벡터 매칭 평면 상에 N개의 점이 찍혀있고, 그 점을 집합 P라고 하자. 집합 P의 벡터 매칭은 벡터의 집합인데, 모든 벡터는 집합 P의 한 점에서 시작해서, 또 다른 점에서 끝나는 벡터의 집합이다. 또, P에 속 www.acmicpc.net [풀이] 단순하게 2개씩 묶는 모든 경우를 고려하면 20C2*18C2....2C2 가 되어 TLE이다. 핵심은 벡터 합이라는 것에 있다. 여러개의 벡터합은 x좌표끼리 연산, y좌표끼리 연산해주면 되기 때문이다. 만약 선분의 길이였다면, sqrt(x^2+y^2)꼴의 sum이라 성분별로 연산이 불가하다. 벡터매칭을 하면, 시작점 N/2개와 종점 N/2개로 나뉜다. 시작점과 종점을 각 집합으로.. 2022. 7. 8.
백준 25332 / C++ https://www.acmicpc.net/problem/25332 25332번: 수들의 합 8 $A = \{1, 2, 3\}$, $B = \{1, 3, 2\}$로, 조건을 만족하는 $i, j$ 쌍은 $(1, 1), (2, 3), (1, 3)$의 세 가지이다. $A_1$ = $B_1 = 1$ $A_2 + A_3 = B_2 + B_3 = 5$ $A_1 + A_2 + A_3 = B_1 + B_2 + B_3 = 6$ www.acmicpc.net [ 풀이 ] B[i]-A[i]=C[i]라고 하자. C[i]+...+C[j]=0 인 (i,j) 쌍을 구하자. C[i]까지 누적합을 pref[i]라 하면, pref[i-1]==pref[j]인 (i,j)를 구하면 된다. 단순하게 O(N^2)에 구하면 TLE이다. 값과 횟수를.. 2022. 7. 7.
백준 1027 / C++ https://www.acmicpc.net/problem/1027 1027번: 고층 건물 세준시에는 고층 빌딩이 많다. 세준시의 서민 김지민은 가장 많은 고층 빌딩이 보이는 고층 빌딩을 찾으려고 한다. 빌딩은 총 N개가 있는데, 빌딩은 선분으로 나타낸다. i번째 빌딩 (1부터 시작) www.acmicpc.net [ 풀이 ] 1. 건물 s와 건물 e가 서로 보일 조건은 두 건물 사이의 건물들의 높이가 두 건물을 이은 직선보다 아래에 있으면 된다. 직선 식을 세워서 보이는지 확인하는 check 함수를 만들어준다. O(N)에 처리할 수 있다. 2. 모든 건물쌍에 대해 check 를 만족하면, cnt[s]와 cnt[e]를 갱신해준다. cnt[i]는 건물i에서 볼수있는 건물의 수이다. 3. 시간복잡도는 각 쌍 N.. 2022. 7. 7.

티스토리툴바