티스토리

ACM-ICPC 상 탈 사람

검색하기

블로그 홈

ACM-ICPC 상 탈 사람

jason9319.tistory.com/m

BOJ Handle : jason9319

구독자: 12

방명록 방문하기

주요 글 목록

AWS 란? AWS(Amazon Web Service)는 아마존닷컴에서 운영하는 클라우드 컴퓨팅(Cloud Computing) 플랫폼이다. 클라우드 컴퓨팅은 제공자 입장에서는 가상화 된 컴퓨터의 리소스를 사용자에게 요구하는 즉시 제공하는 것이고 사용자 입장에서는 인터넷 기반 컴퓨팅의 일종으로 정보를 자신의 컴퓨터가 아닌 클라우드(인터넷)에 연결된 다른 컴퓨터로 처리하는 기술을 의미한다. 쉽게 풀어서 얘기하면 AWS에서 제공하는 컴퓨터를 내가 원격으로 사용할 수 있다고 생각하면 된다. AWS의 모회사인 아마존 닷컴은 세계 최대의 인터넷 쇼핑몰으로 블랙 프라이데이같이 사용자들이 몰리는 기간을 대비하여 서버를 엄~~~~~~~~~~~~청나게 증설시켜 놨는데 이 서버들이 평소 때 놀고 있는 걸 보고 CEO인 제프 베조스가 이.. 공감수 2 댓글수 3 2020. 3. 31.
BOJ)14288 내리 갈굼4 문제:icpc.me/14288 트리에서 질의를 처리하는 문제이다. 우선 dfs를 이용하여 트리의 번호를 reordering 시켜주어 트리를 구간으로 생각해보자. 문제를 풀기 위해서 일반의 경우와 야자의 경우에 업데이트 시켜주는 영역을 다르게 생각해보자 일반의 경우만 생각해본다면 value가 아래로 전파되기 때문에 나의 자식들의 구간에 업데이트 시켜준 뒤, 답을 가져올 때는 해당 지점의 값을 출력하면 될것이다. 야자의 경우에는 value가 위로 전파되므로 나의 위치에 업데이트 시킨 뒤, 답을 가져올 때, 내 자식들의 업데이트 현황을 다 더해주면 되므로, 자식들의 구간의 합을 출력하면 될것이다. 두가지 모두 Fenwick tree를 이용하여 구현 가능하므로 2개의 fenwick tree를 구현하면 문제를 해.. 공감수 0 댓글수 1 2018. 7. 7.
BOJ)14400 편의점2 문제: icpc.me/14400 고객들의 좌표가 주어 질 때 고객들과의 맨하탄 거리의 합의 최솟값을 구하는 문제이다. 문제를 함수로 표현하면 |x-a1|+|y-b1|+|x-a2|+|y-b2|+|x-a3|+|y-b3|+..... 꼴의 최솟값을 구하는 문제가 되는데, 여기서 x의 절댓값 함수들과 y의 절댓값 함수들을 독립 시켜서 보면 |x-a1|+|x-a2|+...|x-an|의 그래프는 한개의 극값(최솟값)을 가지는 unimodal 함수가 됨을 알 수 있다. 따라서 ternary search를 이용하여 문제를 해결 할 수 있다. 12345678910111213141516171819202122232425262728293031323334353637#include #include #include #include .. 공감수 0 댓글수 0 2018. 7. 5.
BOJ)15745 Snow Boots 문제: icpc.me/15745 1~N 영역에 쌓인 눈의 높이가 주어진다. 이제 B개의 신발에 대한 쿼리가 들어오는데 각 쿼리는 Si와 Di를 가진다. Si는 해당 신발을 신고 걸을 수 있는 최대 눈의 높이이고, Di는 한번에 최대로 걸을 수 있는 거리이다. i번 째 신발을 신었을 때 1에서 부터 N까지 갈 수 있는 지 여부를 매 쿼리마다 출력해주면 되는 문제이다. 풀이법은 여러가지가 있는것 같지만 내가 푼 풀이는 오프라인 쿼리 풀이이다. 우선 쿼리를 Si기준으로 역순으로 정렬을 해준 뒤 순서대로 봐준다. 쿼리를 역순으로 본다면, 쿼리를 보면서 점점 못넘는 영역이 늘어날 것이다. 현재 쿼리를 처리할 때 넘을 수 있는 기준은 현재 못넘는 영역중에서 가장 긴 영역이 되므로 역순으로 쿼리를 처리하면서, 못넘는.. 공감수 1 댓글수 0 2018. 7. 3.
BOJ)13274 수열 문제: icpc.me/13274 정렬 된 수열에서 쿼리를 처리하는 문제이다. 쿼리 l r x 는 l~r 구간의 원소에 x를 더해준 뒤 다시 정렬하는 쿼리이다. n이 10만이고 쿼리가 1000개 인데 매번 퀵소트를 실행해주면 1억xlog10만 이므로 1초의 제한 시간에 간당간당한 느낌이다. 따라서 좀 더 빠른 소팅 방법이 필요한데, 정렬 된 구간에서 l~r에 x를 더하게 되면, l~r의 구간은 오름차순을 유지할 것이며, 전체의 구간에서 l~r의 구간을 제외한 구간 역시 오름차순을 유지할 것이다. 이렇게 정렬 된 두 구간에서 서로 가장 앞 원소를 비교하며 insertion sort를 하면 소팅을 O(N)의 시간에 해결할 수 있다. 1234567891011121314151617181920212223242526.. 공감수 0 댓글수 0 2018. 7. 2.
BOJ)15589 Lifeguards (Silver) 문제: icpc.me/15589 n명의 인원이 1차원 구간을 커버하는 데 이중에서 한 인원을 제외했을 때 커버가능한 최대 구간을 출력하는 문제이다. 전체 구간에서 하나를 제외 하였을 때 최대 구간을 구하면 되므로 하나의 구간에서 다른 구간에 영향을 받지 않고 유일하게 커버되는 구간 중 최솟값을 구하여 전체 구간에서 빼주면 답이 된다. 각각의 구간에서 독립적으로 커버하는 구간은 왼쪽에서 부터, 오른쪽에서 부터 , 두번 스위핑하여 구할 수 있다. 자세한 설명은 소스코드로 대신하겠다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546#include #include #include using namespace s.. 공감수 0 댓글수 0 2018. 6. 26.
BOJ)14965 Lozinke 문제: icpc.me/14965 n개의 문자열이 주어질 때, 모든 문자열 s에 대해, s의 substring 중에 현재 보는 문자열을 제외한 나머지 문자열이 되는 개수를 전부합하여 출력하는 문제이다. 직접 비교하면 n^2으로 시간초과를 보게된다. 문자열의 길이가 10이하라는 사실을 이용하여 모든 문자열 s를 해싱해준 뒤 마찬가지로 모든 문자열의 substring을 전부 해싱하여 set과 map을 이용하여 개수를 계산해주면 n*10*10*logn의 시간에 문제를 해결할 수 있다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758#include #include #in.. 공감수 0 댓글수 0 2018. 6. 26.
BOJ)11964 Fruit Feast 문제: icpc.me/11964 최대 포만감의 최대치가 t이고, 오렌지를 먹으면 a만큼 레몬을 먹으면 b만큼 포만감이 오를 때, 최대 포만감을 구하는 문제이다. 단, 조건이 하나 있는데 딱 한번 물을 마시면 현재 포만감을 반으로 줄일 수 있다. 현재 물을 마셨는 지 아닌지를 제약조건으로 둔다면 다이나믹 프로그래밍으로 문제를 해결할 수 있다. dp[i][j]= 포만감이 i이고 제약조건(물을 마셨는 지 여부)이 j일 때 상태의 존재 여부 12345678910111213141516171819202122232425#include #include #include using namespace std;int dp[5000005][2];int t,a,b,r;int main(){ scanf("%d%d%d",&t,&a,&.. 공감수 0 댓글수 0 2018. 6. 25.
BOJ)11046 팰린드롬?? 문제: icpc.me/11046 길이가 최대 100만인 문자열 s가 주어질 때 s의 인덱스 l~r 까지의 부분 문자열이 팰린드롬인지 쿼리마다 출력하는 문제이다. n이 작다면 n^2의 방법으로 해결해줄 수 있지만 n이 크므로 manacher's 알고리즘을 이용하여 해결해주어야 한다. manacher's 알고리즘으로 전처리를 해준 뒤 중심으로 부터의 최대 팰린드롬 길이와 주어진 구간의 길이를 비교해주어 답을 출력해주면 된다. 시간 복잡도는 O(N+M)이다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546#include #include #include #include #include #include using.. 공감수 0 댓글수 0 2018. 6. 25.
BOJ)1222 홍준 프로그래밍 대회 문제: icpc.me/1222 문제를 해석하면 만약 홍준이가 팀원의 수를 k명이라 정했다면 학교 사람의 수가 k로 나누어 떨어지는 학교만 참가할 수 있다. 즉 주어진 수들을 전부 소인수 분해를 하였을 때 i를 소인수로 가진 학교의 개수를 a[i]라고 하면, a[i]가 2이상인 경우에서의 i*a[i]의 최댓값이 답이 된다. 하지만 모든 수의 소인수를 구할 경우 O(N*sqrt(N))으로 시간내에 들어오기에는 조금 무리가 있다. 하지만 수를 받으면서 소인수를 계속 연산하는 방법이 아닌 수를 전부 받아놓고 하나의 수에는 한번의 계산만 하는 방법으로 최적화 시켜 시간내에 통과시킬 수 있다. 이보다 좋은 방법은 모든 수 i에 대하여 자신을 소인수로 가지는 수를 직접 계산해주는 방법이다. 이 방법은 소스코드로 설명.. 공감수 1 댓글수 0 2018. 6. 25.
BOJ)15675 괴도 강산 문제 :icpc.me/15675 모든 보석을 집고, 위치 추적기를 하나도 안 가진 상태가 가능하다면 1을 아니면 0을 출력하는 문제이다. 문제의 조건을 잘 읽어보면 2NF로 모델링이 가능하여 2-SAT을 이용한 풀이가 가능하다. 우선 보석을 고르는 조건은, 보석이 존재하는 행을 a 열을 b라고 하였을 때, a b 중에 하나밖에 선택되지 않으므로 (a&&!b)||(!a&&b) 라는 식이 세워진다. 하지만 이는 CNF가 아니므로 식을 잘 풀어내어 (a||b)&&(!a||!b)로 변형하여 추가해준다. 다음으로 위치추적기를 밟는 경우 다시 그자리에 돌려놔야 하므로 a b 를 모두 선택하거나 a b를 모두 선택하지 않는 경우 중 한 경우가 이루어져야 한다. 즉(a&&b)||(!a&&!b) 라는 식이 세워지고 이를.. 공감수 0 댓글수 0 2018. 6. 24.
advanced disjoint set 오늘은 disjoint set에 대해서 글을 적어보겠습니다. 직역하면 상호배타적 집합이며, union-find 라는 자료구조로 표현됩니다. [disjoint set, DSU(disjoint union),union find] 는 전부 union find 자료구조를 칭하는 말입니다. union find 는 union연산과 find연산을 매우 빠르게 해주는 자료구조로서, 상호배타 집합에서는 어떠한 집합에서도 공통 된 원소가 존재하지 않으며, 동시에 모든 집합의 합집합은 전체집합이 됩니다. 이해를 돕기 위하여 특수한 상황을 가정해보겠습니다. a라는 나라와 b라는 나라가 동맹이고, b라는 나라와 c라는 나라가 동맹을 맺게된다면 a와 c나라도 자동으로 동맹이 되는 경우를 생각해봅시다. 해당 경우로 각각의 나라의 동.. 공감수 3 댓글수 2 2018. 6. 24.
BOJ)13016 내 왼손에는 흑염룡이 잠들어 있다 문제: icpc.me/13016 오랜만에 문제 포스팅을 한다. 문제를 요약하면 한 정점 v에서 다른 정점으로의 최단거리를 dist[i] (i: 1~n) 이라고 했을 때, dist[i]의 최댓값을 모든 정점 v에 대해 구하는 문제이다. 물론 한 정점에서 dist[i]의 최댓값을 구하는건 dfs를 수행하여 쉽게 해결할 수 있지만 모든 정점에 대해 구하게 될 경우 정점의 개수가 5만이므로 시간초과를 보게 될 것이다. 하지만 조금 생각해보면 한 정점에서의 부터 다른 정점으로 부터의 최단 거리 중 최댓값은 트리의 지름의 양 끝 단말 노드 중 하나로의 거리라는 것을 알 수 있다.(만약 트리 지름의 단말 노드가 아닌 다른 리프로 부터의 거리가 최댓값이라면, 트리의 지름보다 긴 거리가 생긴다는 뜻이므로 모순이된다.) .. 공감수 0 댓글수 0 2018. 6. 24.
SCPC 2018 이벤트 당첨! 살면서 이런 이벤트와는 인연이 없다고 생각했는데 어제 갑자기 문자가 왔다. 커피 당첨됬다고 ㅋㅋㅋ 올해 SCPC는 본선에 나갈 수 없겠지만(7월 입사 ㅠㅠ... 게다가 일본 여행 날짜와 2차 예선 날짜가 겹친다 ...) 커피라도 받게되서 기분이 좋다 공감수 0 댓글수 6 2018. 6. 23.
BOJ)15673 헤븐스 키친2 문제 :http://icpc.me/15673 n개의 수열이 주어질 때, 연속 된 두 구간을 선정을 한다. 두 구간을 a,b라하면 구간 a의 합과 구간 b의 합의 곱의 최댓값을 구하는 문제이다. 생각해보면 구간 a의 합과 구간 b의 합의 최솟값들을 곱하는 경우와, 구간 a의 합과 구간 b의 합의 최댓값들을 곱하는 경우가 답의 후보가 됨을 알 수 있다. 구간 a가 i~j 구간 b가 k~l 이라고 해보자. k를 고정시킨 뒤 생각해보면 구간 k~l의 합은 psum[l]-psum[k-1]이므로, k보다 크거나 같은 범위의 psum의 최댓값과 최솟값을 가지고 있으면, 구간 b의 최댓값과 최솟값을 구할 수 있다. 그럼 i~j 구간의 최댓값과 최솟값은 어떻게 처리할 수 있을까? 구간 i~j의 합은 psum[j]-psu.. 공감수 0 댓글수 1 2018. 5. 6.
BOJ)1856 단어 게임 문제: icpc.me/1856 w개의 문자열이 주어진다.길이 l의 문자열을 앞서 주어진 w개의 문자열로만 표현하고 싶을 때 지워야하는 문자의 최소 개수를 출력하는 문제이다.dp[x]=길의 l의 문자열을 길이 x까지 봤을 때 지워야하는 최소 문자의 수로 정의한 뒤 점화식을 세우면dp[x]를 채우기 위해선 w개의 각각의 문자열에 대해서 저 문자를 남기기 위하여 지워야할 개수를 구해주면 l*l*w의 시간복잡도로 디피 테이블을 채울 수 있다. 123456789101112131415161718192021222324252627282930313233343536373839#include #include #include #include #include using namespace std;int w,l,dp[333];st.. 공감수 0 댓글수 2 2018. 3. 29.
BOJ)2171 직사각형의 개수 문제: icpc.me/21712차원 평면위에 5000개 이하의 점이 있을 때 점들로 만들 수 있는 모든 직사각형의 수를 세는 문제이다,n제한이 5000에 2초이므로 n^2logn 솔루션으로 풀 수 있을 것이라고 생각하였다.n*n으로 모든 두 점에 대하여 직사각형의 대각선에 놓이는 경우를 생각하면, 나머지 대각선에 포함되는 두 점은 set을 이용해 존재여부를 log시간에 찾을 수 있다.123456789101112131415161718192021222324252627#include #include #include #include using namespace std;int n,res;set st;vector vt;int main(){ scanf("%d",&n); for(int i=0;i 공감수 0 댓글수 0 2017. 12. 19.
BOJ)14943 벼룩 시장 문제: icpc.me/14943벼룩을 사려는 사람과 팔려는 사람이 있을 때 벼룩 거래에 발생하는 비용의 최솟값을 출력하는 문제이다.문제를 잘 읽어보면 사려는 양과 팔려는 양은 같고, 거래에 발생하는 비용이 거래하는 두 사람의 거리에 비례한다.우선 사려는 양과 팔려는 양이 같다는 점을 이용해, 항상 거래가 완전하게 이루어진다는 점을 생각해보면, 그냥 최대한 가깝게 거래를 매칭 시켜주는 그리디한 방법이 답이 된다는 걸 알 수 있다.문제는 n이 10만으로 조금 크기 때문에 매칭을 일일이 직접 해줄 수는 없고, 투 포인터를 이용하여 처리해주면 깔끔하게 구현 가능하다.1234567891011121314151617181920212223242526272829303132333435363738#include #inclu.. 공감수 0 댓글수 0 2017. 12. 18.
BOJ)14950 정복자 문제:icpc.me/14950모든 도시를 점거하는데 필요한 최소 비용을 출력하는 문제이다.단 도시를 점거 해 나갈 때 마다 일정 비용이 추가 되었는 데 이것에 포커스를 맞추면 문제가 어려워 질 수 있다.조금 생각을 해보면 결국 모든 도시를 점거해야하기 때문에 MST를 만들어주면 비용을 커버할 수 있는 걸 알 수 있다.이미 MST를 구상하였다면 이에 이용 된 간선은 n-1개로 고정일 것이고, 이는 모든 도시를 점거하는데 필요한 간선의 최소 개수이기도 하기 때문에(1~n-1 까지의 합) x t가 증가하는 비용으로 고정된다.123456789101112131415161718192021222324252627282930313233343536373839#include #include #include using nam.. 공감수 0 댓글수 0 2017. 12. 12.
BOJ)15271 친구 팰린드롬2 문제: icpc.me/15271남자와 여자에 대한 이분 그래프가 형성되므로 이분 매칭으로 최대로 세울 수 있는 친구 수를 구해줄 수 있다.1234567891011121314151617181920212223242526272829303132333435363738394041424344#include #include #include #include using namespace std;int n, m, visited[222], b[222];vector vt;int dfs(int here) { if (visited[here])return false; visited[here] = true; for (auto next : vt[here]) { if (!b[next] || dfs(b[next])) { b[next] = .. 공감수 0 댓글수 0 2017. 12. 5.
BOJ)15270 친구 팰린드롬 문제: icpc.me/15270 명시 된 N의 범위가 작으므로 상태DP를 이용하여 해결할 수 있다.dp[state][pos] = state(이미 친구가 된 사람들의 상태를 표현)이고 pos번째 까지 친구 관계를 봤을 때 춤을 추는 인원의 최댓값12345678910111213141516171819202122232425262728#include #include #include using namespace std;int dp[1 공감수 0 댓글수 0 2017. 12. 5.
BOJ)14939 불 끄기 문제: icpc.me/14939 언제 봤는지는 기억이 잘 안 나지만 언젠가 한번 봤었던 은근히 well-known 문제이다.첫 줄에 전구를 어떤 방식으로 뒤집는 걸 결정을 했다고 가정하면 그 아래 줄은 바로 위의 전구가 켜져 있는지 여부에 따라서 뒤집기 결정을 그리디하게 할 수 있다.따라서 첫 줄을 뒤집는 모든 경우 (2^10)에 대하여 정해준 뒤, 그리디하게 뒤집어주어 최적의 답을 구하는 것이다. 비슷한 시기에 나온 홍익대학교 경시대회의 전구 끄기 문제도 한번 풀어보면 좋을 것 같다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859#include #incl.. 공감수 0 댓글수 0 2017. 12. 4.
BOJ)14938 서강그라운드 문제: icpc.me/14938 n의 범위가 작고 다대다 최단거리를 필요로 하기 때문에 플로이드 워셜 알고리즘을 사용할 수 있다.플로이드 워셜 알고리즘으로 모든 정점쌍의 최단거리를 구해준 후 , 모든 정점을 기준으로 얻을 수 있는 아이템의 개수를 세준 뒤 그 중에 최댓값을 출력해주면 된다. 123456789101112131415161718192021222324252627282930313233343536#include #include #include using namespace std;int n, m, r, item[111], a[111][111], res;int main() { memset(a, 0x3f, sizeof(a)); scanf("%d%d%d", &n, &m, &r); for (int i = 1.. 공감수 0 댓글수 0 2017. 12. 4.
BOJ)14936 엘리베이터 장난 문제: icpc.me/14936 엘리베이터에서 m초 동안 4가지 동작을 수행할 수 있는데, m초가 지났을 때 버튼의 모습의 경우의 수를 세는 문제이다.n,m제한이 상당히 크고, 경우의 수를 구하는 문제이므로 어렵게 접근할 수 있으나, 이는 함정이고어짜피 같은 동작을 두 번 수행할 경우 원점으로 돌아가게 되기 때문에 모든 경우를 생각해볼 수 있다.모든 경우의 수는 결국 x번 버튼을 누르는 경우의 퍼뮤테이션 이기에4P0+4P1+4P2+4P3+4P4개 밖에 되지 않는다. 따라서 저 모든 경우에 대하여 직접 버튼을 뒤집어주어도 충분히 시간 내에 동작 할 수 있다.930313233343536373839404142434445464748495051525354555657#include #include #include .. 공감수 0 댓글수 0 2017. 12. 4.
일산 주렁주렁 토요일인 어제 자다가 친구가 하남을 가자고 하길래 잠결에 OK하고 나갔다.사실 어디가는지도 모르고 따라 나선거였는데 네비게이션에 주렁주렁이라고 적는걸 보고하남->돼지집 / 주렁주렁->주경야돈 / 이 떠올라서 고기집 가는구나~ 했는데 알고보니 애니멀 테마파크를 가는거 였다.그런데 잘 알아보니 일산쪽이 더 저렴하고 인천에서 출발하기에 길도 안막힐 것 같아서 일산에 있는 주렁주렁으로 가게 되었다.동물을 평소에 좋아하는 편은 아니지만 싫어하는 편도 아니여서 가벼운 마음으로 갔다.그런데 내가 생각하던 것 보다 테마파크가 잘 되있다고 느꼈다.거의 초반부터 앵무새를 볼 수 있었는데 색감이 너무 예뻤다. 그리고 여기 동물들은 뱀 같은 동물을 제외하면 그냥 개방 된 공간에 노출되어 직접 만져볼 기회도 있고, 먹이 주기 .. 공감수 0 댓글수 2 2017. 11. 19.
BOJ)11670 초등 수학 문제: icpc.me/11670n개의 줄에 순서 쌍 a,b가 주어진다. 각 a,b에 대하여 a+b또는a-b또는a*b 에 일치하는 수들이 중복 없이 n개 존재한다면 그 답을 출력하는 문제이다.이 문제는 잘 생각해보면 순서 쌍 a,b와 답이 될 수 있는 후보인 수들의 이분 그래프로 모델링 할 수 있다.따라서 답을 구하기 위하여 이분 매칭을 구해주어 최대 매칭이 n이 된다면 답을 역추적하여 구해주고, n이 안된다면 impossible을 출력하면 된다.12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970#include #includ.. 공감수 0 댓글수 0 2017. 11. 15.
BOJ)3136 평면도 문제: icpc.me/3136좌표평면에 주어진 순서대로 그림을 그릴 때 평면도 상에서 존재하는 모든 방의 개수를 출력하는 문제이다.평면 그래프에서 V-E+F=2 라는 공식이 성립한다는 점을 이용하여 문제를 해결할 수 있다.(V:정점의 수, E:간선의 수,F:평면의 수)구해야 하는게 평면의 수 이므로 평면의 수는 F=2-V+E로 구할 수 있다. 하지만 좌표 평면 전체도 하나의 평면으로 세므로 답은 1-V+E가 된다.이제 V의 수와 E의 수를 구해야 하는데 이는 set을 이용하여 세주면 편리하게 계산할 수 있다.이 때 주의해야 할 점이 대각선으로 만나는 점을 처리해주기 위해 한 방향으로 나아갈 때 두번씩 나아가도록 점을 찍어주어야 한다. 자세한 것은 소스를 보며 이해하도록 하자.1234567891011121.. 공감수 0 댓글수 0 2017. 11. 15.
BOJ)14195 DotB 문제: icpc.me/14195각 테스트 케이스마다 n과 c가 주어진다. 이후 n개의 시퀀스가 주어진다.이제 0번 인덱스부터 증가하는 순서로 보면서 시퀀스를 c만큼 감소시킬 것이다. 해당 원소가 0이하가 되면 시퀀스의 탐색 방향을 반대방향으로 바꾸고 해당 원소를 제거한다.이렇게 하였을 때, n+5번 탐색을 하였을 때 가장 마지막에 감소 된 원소의 번호를 출력하는 문제이다.n이 적은편이기 때문에 시뮬레이션을 돌려주면 된다.1234567891011121314151617181920212223242526272829303132333435363738394041424344#include #include #include using namespace std;int t, r, n, c;int func(vector vt, .. 공감수 0 댓글수 0 2017. 11. 15.
ACM ICPC 대전 리저널 후기 빼빼로 데이에 대전 리저널을 치게 되었다.바로 전날인 11월 10일에 면접일정이 잡혀 예비 소집을 못 가고 면접이 끝나자마자 부랴부랴 대전으로 향했다.그렇게 다음날 그토록 기다리던 대전 리저널에 참가했고 망했다.이번 롤드컵 때 페이커가 말했던 간절함이 부족했다는 구절이 생각났다.사실 인터넷 예선이 끝나고 대전 리저널 까지의 기간 동안 거의 코딩을 놨다.지쳐서 그랬을 수도 있고, 자만해서 그랬을 수도 있고, 안도하여 그랬을 수도 있다.왜 그랬는지는 웃기게도 나도 잘 모르겠다. 예선에 나온 FFT를 팀노트에 준비 안한 점 , BOJ에서 풀어봤던 문제랑 유사한 문제를 못 푼 점.. 등등 아쉬운 점도 많지만대회가 끝난 시점에 난 시원섭섭하면서도 속상하였다.대회 당일 날 시상식 때 생각보다 덜 슬퍼서, 결과에 덜.. 공감수 3 댓글수 4 2017. 11. 15.
BOJ)14748 Flow Graph Complexity 문제: icpc.me/14748 주어진 문자열로 만들 수 있는 그래프의 C값을 구하는 문제이다.C값은 EF+W*EB-V+2 로 구할 수 있다.즉 주어진 문자열을 잘 파싱하여서 EF, EB, V 세 값을 구해내면 되는 문제이다.하지만 문제에서 valid하지 않은 경우가 주어지는데 이는 일단 생각하지 말고 주어진 조건에 따라서 그래프를 그리게 된다면 EB가 생기는 경우는 무조건 L이 있는 경우이다 즉, EB의 수는 L이 등장하는 횟수이다.V가 생기는 경우는 S일 때는 하나가 생기며, L이나 B의 경우 하나가 더 생겨서 2개가 생긴다.즉 V의 수는 S+2*L+2*B 이다. 마지막으로 EF의 수는 각 정점은 마지막 정점을 제외하고 모두 아래로 하나씩 EF를 쏜다. (L에 의하여 생기는 정점은 간선을 받지 않지만.. 공감수 0 댓글수 0 2017. 10. 24.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.