수학20 백준 25339 / C++ https://www.acmicpc.net/problem/25339 25339번: 반전 수와 쿼리 1부터 $N$까지의 수가 한 번씩 등장하는 수열 $P = \lbrace 1, 2, \cdots, N \rbrace$이 주어진다. 수열 $P$에 대해, $i P_j$를 만족하는 순서쌍 $(i, j)$의 개수를 $P$의 반전 수라고 정의하자. 이 www.acmicpc.net 쿼리마다 반전수의 홀짝성을 확인해주는 문제이다. 수학이 전부인 문제. [ 풀이 ] // 1번 쿼리의 경우 Ai와 Aj를 교환한다고 하자. Ai와 Aj 사이의 수열에만 관심이 있다. 나머지 A1~Ai-1, Aj+1~An은 Ai와 Aj가 교환되도 반전수에 영향이 없다. Ai+1~Aj-1중 Ai와 반전쌍을 이루는 것의.. 2022. 7. 12. 백준 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. 백준 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. 이전 1 2 3 4 5 다음