전체 글 (74) 썸네일형 리스트형 [BOJ 5846] Wifi Setup https://www.acmicpc.net/problem/5864 5864번: Wifi Setup Farmer John's N cows (1 N>>A>>B; for(int i=1;i>v[i]; v[i]*=2; } sort(v+1,v+1+N); for(int i=1;i [BOJ 10403] Intrepid climber https://www.acmicpc.net/problem/10403 10403번: Intrepid climber The first line contains two integers N and F (1 ≤ F < N ≤ 105), representing respectively the number of landmarks and the number of your friends that are climbing the mountain. Landmarks are identified with distinct integers from 1 to N, being 1 the to www.acmicpc.net Tag : Greedy, Tree dp 문제요약 트리 위에 F개의 랜드마크가 존재하는데, 1번노드에서 출발해 모든 랜드.. [BOJ 20531] 인간관계 https://www.acmicpc.net/problem/20531 20531번: 인간관계 S인터넷고등학교에는 $N$명의 학생이 있다. 이들 사이에 몇몇은 서로 친구 관계를 맺고 있다. 친구 관계는 다음 세 가지 조건을 만족한다. 모든 학생은 자기 자신의 친구이다. 학생 $x$가 학생 $y$ www.acmicpc.net Tag : combinatorics, prefix sum 문제 요약 N명의 사람을 K개의 그룹으로 분할하는 경우의 수 \(dp_{N,K}\)는 \(\sum{\binom{N}{j}*dp_{N-j,K}}\)처럼 표현할 수도 있지만 좀 계산하기 쉬운 형태로도 나타낼 수 있다. \(dp_{i,j}=dp_{i-1,j-1} + j \times dp_{i-1,j}\) 이 식을 토대로 계산만 해주면 된.. [BOJ 11997] Load Balancing (silver) https://www.acmicpc.net/problem/11997 11997번: Load Balancing (Silver) Farmer John's \(N\) cows are each standing at distinct locations \((x_1, y_1) \ldots (x_N, y_N)\) on his two-dimensional farm (\(1 \leq N \leq 1000\), and the \(x_i\)'s and \(y_i\)'s are positive odd integers of size at most \(1,000,000\)). FJ wants to par www.acmicpc.net Tag : brute force, prefix sum, coordinate compression 문.. [BOJ 23569] Friendship Graph https://www.acmicpc.net/problem/23569 23569번: Friendship Graphs Given a collection of people who interact, we can define a graph whose vertices are people, with an edge between two people if and only if they are friends with one another. Such graphs are called social networks and are well defined on any set of people, www.acmicpc.net Tag : graph theory, knapsack dp 문제요약 주어진 그래프를 두개의 clique로 쪼개라... [BOJ 20968] Group Photo https://www.acmicpc.net/problem/20986 20986번: Group Photo At the end of a training camp, a group photo is taken with the N participants.The participants are numbered from 1 to N, in order of height. The height of the participant h is h (1 ≤ h ≤ N). The participants stand on the stairs for the photo. There are www.acmicpc.net Tag : dynamic programming, prefix sum 문제요약 수열 \(A\)의 인접한 두 원소들을 swap해가면.. [BOJ 17927] Counting Greedily Increasing Supersequences https://www.acmicpc.net/problem/17927 17927번: Counting Greedily Increasing Supersequences Given a permutation $A = (a_1, a_2, \dots, a_N)$ of the integers $1, 2, \dots, N$, we define the greedily increasing subsequence (GIS) in the following way. Let $g_1 = a_1$. For every $i > 1$, let $g_i$ be the leftmost integer in $A$ that is strictly larg www.acmicpc.net Tag : combinatorics, number theory 문.. 선린 가을맞이 알고리즘 챌린지 Solution 안녕하세요 선린인터넷고등학교 정보보호과 2학년으로 재학중인 김채완입니다. 선린 가을맞이 알고리즘 챌린지의 문제 중 제가 출제한 것은 E, F, G, J이며 이 문제들의 풀이를 작성하려합니다. E. 구름 다리 2 Tag : Greedy 인접한 것들은 서로 다른 색을 칠할 때 사전순으로 가장 앞서는 색 조합을 구하는 문제이다. 번호가 작은 것부터 가능한 가장 작은 수를 배치하는 것이 항상 최적이다. 현재 정점을 \(X\)라 하면 \(X\)와 인접한 것들 중 \(X\)보다 작은 것들만 고려한 \(mex\)를 구하면된다. \(mex\)는 주어진 집합에 속하지 않는 가장 작은 음이 아닌 정수를 의미한다. 이 문제에서는 색이 1부터 시작하는 점을 주의해야한다. 시간복잡도 : \(O((N + M)logM)\) 전체 .. 이전 1 ··· 5 6 7 8 9 10 다음
