전체 글178 백준 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)의 세 가지이다. A1 = B1=1 A2+A3=B2+B3=5 A1+A2+A3=B1+B2+B3=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. 이전 1 ··· 42 43 44 45 다음