본문 바로가기

전체 글188

백준 1111 / C++ https://www.acmicpc.net/problem/1111 1111번: IQ Test 다음 수를 출력한다. 만약 다음 수가 여러 개일 경우에는 A를 출력하고, 다음 수를 구할 수 없는 경우에는 B를 출력한다. www.acmicpc.net 수열이 규칙성을 만족하는지 확인하고 유일하면 출력까지 하는 문제이다. 일단 규칙이 p*전항+q 이므로 미지수가 2개이다. 따라서 a1, a2, a3만으로 p와 q는 결정된다. (항이 3개 이상일때) // 항이 3개 이상 p=(a3-a2)/(a2-a1)이 된다. p가 정수면, q도 정수이므로 a3-a2가 a2-a1의 배수인지만 체크해주자. (예외처리는 a1=a2일때) 이렇게 해서 정수 p, q를 찾았다. 이제 수열을 1번 돌면서 모두 이 규칙인지 확인한다. 잘 가다.. 2022. 7. 9.
백준 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.

티스토리툴바