생각날때마다 올리는 블로그

링크http://icpc.me/1185문제1. 모든 마을을 최소 한 번씩은 방문해봐야 한다.2. 반드시 출발한 곳으로 돌아와야 한다.3. 출발점은 "임의로" 설정할 수 있다. 이 때 최소 코스트를 출력하라 풀이핵심은 "다시 돌아와야 한다"라는 것이다.일단, 출발점은 임의로 설정할 수 있고, MST 특성 상 어떤 곳에서 시작해도 상관이 없음을 생각하면그냥 그리디스럽게 방문할 때 가장 작은 코스트가 드는 곳에서 시작하면 된다.예제를 생각해보면, 4번 마을을 방문할 때 코스트가 6으로 제일 적으므로 4번에서 시작하는 것이다.이제 어떻게 방문할지를 생각해봐야 한다. 관찰을 해보면, 다시 자기자신으로 돌아와야 한다는 특징 때문에, 간선을 무조건 "짝수"번 들러야 함을 알 수 있다.MST 특성 상 사이클은 없으므로..

링크http://icpc.me/7453 문제네 개의 배열 A, B, C, D가 주어질 때, A[a]+B[b]+C[c]+D[d]=0이 되는 (a, b, c, d)의 순서쌍의 갯수즉, 걍 아무거나 네 개 뽑아서 더했을 때 0되게 하는 갯수 풀이먼저, $N\leq4000$임을 생각해야한다.이를 왜 생각해야하느냐?만약 완전탐색 기법으로 A, B, C, D 모든 배열 훑으면서 쓰으으윽 하면 $O(N^4)$이된다.$4000=4\times10^3$이고, $4000^4=2^8\times10^{12}$인데 이를 1초내에 돌리는건 그냥 불가능하다...따라서 좀 더 효율적은 방법을 생각해보아야 한다! Key-Idea : Meet in the Middle영어로 까리하게 Meet in the middle인데 한국어로 직역하면 ..

https://www.acmicpc.net/problem/1071문제$N$개의 숫자가 주어진다. 이 때, $A[i]+1\neq A[i+1]$이 되지 않게 숫자의 순서를 바꾸고자 한다.만약 답이 여러개면 사전순으로 제일 빠른 것을 출력하라. 풀이풀이의 시작은 제일 빠른에 있다.제일 빠른 것을 출력할려면 일단 숫자를 최대한 작게 하되 "필요할 때만" 바꿔줘야 한다.예를 들어서 1 3 4 4 이렇게 있으면 굳이 안바꿔도 위 조건을 만족시키기 때문에 상관이 없다는 것이다.하지만 3 4 4 1 이렇게 인풋이 들어오면 1이 제일 앞에 오게 바꿔줘야 한다. 따라서 먼저 들어온 input들을 정렬해서 그 이후 순서를 적절히 바꿔줘야 함을 알 수 있다.이제 정렬되었다고 가정하자. $A_i,\ A_{i+1},\ \cdot..

문제친목하기 위해 7명의 그룹을 만드는데, 지배하기 위해 공주파가 최소 4명있어야한다.5*5 행렬에서 얼마나 많은 그룹을 만들 수 있을것인가? 해설백트래킹 기법을 이용하는데, 조금 창의적으로 활용한다.이 문제를 풀기 위해 미리 알고 있으면 좋은 문제는 유명한 로또 문제이다.7/45 로또 아님 ㅎ로또 문제의 링크는 다음과 같다http://icpc.me/6603 이 문제는 주어진 수 집합(7~9개) 중 7개를 고르는 문제이다.이걸 활용한다.일단 5*5로 되어있는 행렬을 한줄로 펼치고, 차례대로 인덱스를 붙이자.(0,0)에 있는건 0, (0,1)에 있는건 1.... 이렇게(i,j)에 있는건 5*i+j의 인덱스를 가지게 된다.그 다음 로또에서 사용했던 백트래킹 기법으로 7개를 뽑는다.뽑은 후에 우리가 볼건 2가..

http://codeforces.com/problemset/problem/622/D 문제$\displaystyle\sum_{i=1}^{n}{(n-i)\left|d_i+i-n\right|}$ 의 최소값이 되게하는 배열을 구하여라.여기서, $d_i$는 배열 a에서 (i가 두 번째로 나타나는 위치) - (i가 첫 번쨰로 나타나는 위치)를 의미한다. 키포인트곱해주는 값이 둘다 0보다 크거나 같은 양수이므로, 모든 항의 값을 0으로 만들 수 있는 방법에 대해 고민해본다. 1) i=n0이다. 자명 2) i$\neq$n뒤의 절댓값을 0으로 맞출 생각해보자. i

문제 링크https://www.acmicpc.net/problem/5475https://oj.uz/problem/view/IOI07_miners 문제 요약광부들은 자신이 최근에 먹은 세 끼의 종류에 따라 캐는 석탄의 양이 달라진다. 다 다를 경우 3, 두 종류 일 경우 2, 한 종류 일 경우 1이다.들어오는 식사의 개수의 종류는 3개이고, 광산은 총 2개 있다. 식사가 들어가지 않으면 0개의 석탄이 생산된다. 광부들이 최대로 생산해낼 수 있는 석탄의 양을 구하여라. dp 배열들의 정의와 그것을 통한 아이디어 끌어오기cost[i][j][k]=음식의 순서가 차례대로 i,j,k로 들어왔을 때 얻을 수 있는 석탄의 양비어 있는 경우는 3으로 정의한다.비어 있는 경우는 맨 처음 생기게 된다. 아무것도 없는 상황에..

문제 링크https://www.acmicpc.net/problem/5466https://oj.uz/problem/view/IOI09_salesman 문제 요약상인이 어떤 마을의 시장에서 다른 마을의 시장으로 가서 이득을 취할려고 한다.위로 올라갈 때에는 U의 비용이, 아래로 내려갈 때에는 D의 비용이 들고, 각 마을의 위치는 $P_i$,각 마을에서 얻을 수 있는 이득은 $M_i$이다.각 마을의 시장이 열리는 날은 $D_i$이며, 마지막에 방문한 곳에서 집으로 꼭 와야한다. 집의 좌표는 S이다.이 때, 상인이 얻을 수 있는 최대 이득은 얼마인가? 간단한 DP( Subtask 1, $N\leq5000$ )dp[i] : i번째시장까지 얻을 수 있는 상인의 최대 이득최초엔 상인은 집의 위치에 있고, 마지막엔 항..

icpc.me/5465https://oj.uz/problem/view/IOI09_mecho문제 요약1초마다 현재 별들이 있는 위치에서 별들이 사방으로 퍼진다고 한다. 곰돌이는 현재 위치에서 최대한 많이 꿀을 빨아먹고 벌에 물리지 않고 집을 가고 싶어한다.과연, 얼마나 많은 꿀을 빨아먹을 수 있을것인가? 단, 곰돌이는 1초에 S번 움직일 수 있고, 곰돌이는 현재 위치에서 상하좌우로 이동할 수 있다. 관찰만약, T일 동안 꿀을 빨고, 출발해도 충분히 집에 도달할 수 있다고 하자. 그럼, T-n ( 0 < n = pre[sx][sy]) return false; queue q; q.push(make_pair(make_pair(sx,sy),time*s)); reach[sx][sy]=1; while(!q.empty..

문제 링크https://oj.uz/problem/view/JOI14_secret 문제 요약 어떤 연산자 ★이 있다.얘가 결합법칙은 성립한다. 즉, (x★y)★z = x★(y★z)가 성립한다.이 때, 주어진 배열 A에서, 우리는 구간 L,R이 주어질 때,A[L] ★ A[L+1] ★ A[L+2].... ★ A[R]의 값을 알아내라. 함수형우리는 Secret란 함수를 통해서 x와 y의 ★의 값을 알 수 있다,우리가 구현해야하는 함수는 2개이다.두 함수는 다음과 같다. 1) Init(int N,int A[])N은 배열에 들어가있는 숫자의 개수이고, A는 배열을 나타낸다.초기화 단계로, 100점을 맞기 위해서는 Secret 함수를 최대 8000번 불러내야한다. (N

https://oj.uz/problem/view/JOI14_pinball 문제i번째에 사이에 있는 모든 좌표들을 로 보내버리는 핀볼 막대기가 위치하고, 각 막대기를 한 번 탈때마다 D_i의 비용이 듭니다.이 때, 어떤 좌표에서 떨어트려도 똑같은 좌표로 놓게 하는 핀볼의 배치 중에서, 최소의 비용이 드는 핀볼의 위치의 배치를 찾아서 그 비용이 얼마인지를 구하여라. 관찰이 문제를 그냥 아무 생각 없이 보면 상당히 복잡한 시뮬레이션 게임처럼 보인다. 하지만, 일종의 가정을 하고 나면 그 순간부터는 생각보다 간단한 문제로 바뀐다.공의 최종 위치를 항상 단조 증가하게 막대기를 놓는다고 하자. 이렇게 하면, 결론적으로 모든 공이 다 한쪽으로 모이기 위해선, 1번 공과 N번 공이 똑같은 곳으로 모이면 된다.나오는 출..