본문 바로가기

분류 전체보기

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.. 더보기
BOJ)14936 엘리베이터 장난 문제: icpc.me/14936 엘리베이터에서 m초 동안 4가지 동작을 수행할 수 있는데, m초가 지났을 때 버튼의 모습의 경우의 수를 세는 문제이다.n,m제한이 상당히 크고, 경우의 수를 구하는 문제이므로 어렵게 접근할 수 있으나, 이는 함정이고어짜피 같은 동작을 두 번 수행할 경우 원점으로 돌아가게 되기 때문에 모든 경우를 생각해볼 수 있다.모든 경우의 수는 결국 x번 버튼을 누르는 경우의 퍼뮤테이션 이기에4P0+4P1+4P2+4P3+4P4개 밖에 되지 않는다. 따라서 저 모든 경우에 대하여 직접 버튼을 뒤집어주어도 충분히 시간 내에 동작 할 수 있다.930313233343536373839404142434445464748495051525354555657#include #include #include .. 더보기
일산 주렁주렁 토요일인 어제 자다가 친구가 하남을 가자고 하길래 잠결에 OK하고 나갔다.사실 어디가는지도 모르고 따라 나선거였는데 네비게이션에 주렁주렁이라고 적는걸 보고하남->돼지집 / 주렁주렁->주경야돈 / 이 떠올라서 고기집 가는구나~ 했는데 알고보니 애니멀 테마파크를 가는거 였다.그런데 잘 알아보니 일산쪽이 더 저렴하고 인천에서 출발하기에 길도 안막힐 것 같아서 일산에 있는 주렁주렁으로 가게 되었다.동물을 평소에 좋아하는 편은 아니지만 싫어하는 편도 아니여서 가벼운 마음으로 갔다.그런데 내가 생각하던 것 보다 테마파크가 잘 되있다고 느꼈다.거의 초반부터 앵무새를 볼 수 있었는데 색감이 너무 예뻤다. 그리고 여기 동물들은 뱀 같은 동물을 제외하면 그냥 개방 된 공간에 노출되어 직접 만져볼 기회도 있고, 먹이 주기 .. 더보기
BOJ)11670 초등 수학 문제: icpc.me/11670n개의 줄에 순서 쌍 a,b가 주어진다. 각 a,b에 대하여 a+b또는a-b또는a*b 에 일치하는 수들이 중복 없이 n개 존재한다면 그 답을 출력하는 문제이다.이 문제는 잘 생각해보면 순서 쌍 a,b와 답이 될 수 있는 후보인 수들의 이분 그래프로 모델링 할 수 있다.따라서 답을 구하기 위하여 이분 매칭을 구해주어 최대 매칭이 n이 된다면 답을 역추적하여 구해주고, n이 안된다면 impossible을 출력하면 된다.12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970#include #includ.. 더보기
BOJ)3136 평면도 문제: icpc.me/3136좌표평면에 주어진 순서대로 그림을 그릴 때 평면도 상에서 존재하는 모든 방의 개수를 출력하는 문제이다.평면 그래프에서 V-E+F=2 라는 공식이 성립한다는 점을 이용하여 문제를 해결할 수 있다.(V:정점의 수, E:간선의 수,F:평면의 수)구해야 하는게 평면의 수 이므로 평면의 수는 F=2-V+E로 구할 수 있다. 하지만 좌표 평면 전체도 하나의 평면으로 세므로 답은 1-V+E가 된다.이제 V의 수와 E의 수를 구해야 하는데 이는 set을 이용하여 세주면 편리하게 계산할 수 있다.이 때 주의해야 할 점이 대각선으로 만나는 점을 처리해주기 위해 한 방향으로 나아갈 때 두번씩 나아가도록 점을 찍어주어야 한다. 자세한 것은 소스를 보며 이해하도록 하자.1234567891011121.. 더보기
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, .. 더보기
ACM ICPC 대전 리저널 후기 빼빼로 데이에 대전 리저널을 치게 되었다.바로 전날인 11월 10일에 면접일정이 잡혀 예비 소집을 못 가고 면접이 끝나자마자 부랴부랴 대전으로 향했다.그렇게 다음날 그토록 기다리던 대전 리저널에 참가했고 망했다.이번 롤드컵 때 페이커가 말했던 간절함이 부족했다는 구절이 생각났다.사실 인터넷 예선이 끝나고 대전 리저널 까지의 기간 동안 거의 코딩을 놨다.지쳐서 그랬을 수도 있고, 자만해서 그랬을 수도 있고, 안도하여 그랬을 수도 있다.왜 그랬는지는 웃기게도 나도 잘 모르겠다. 예선에 나온 FFT를 팀노트에 준비 안한 점 , BOJ에서 풀어봤던 문제랑 유사한 문제를 못 푼 점.. 등등 아쉬운 점도 많지만대회가 끝난 시점에 난 시원섭섭하면서도 속상하였다.대회 당일 날 시상식 때 생각보다 덜 슬퍼서, 결과에 덜.. 더보기
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에 의하여 생기는 정점은 간선을 받지 않지만.. 더보기
BOJ)5846 Tractor 문제: icpc.me/5846 n^2의 격자에서 한 점에서 4방향으로 일정 조건(둘의 차이가 k이하이면 이동 가능)을 만족하면 이동가능할 때임의의 한점을 잡아 반 이상의 격자를 순회할 수 있는 최소의 k를 찾는 문제이다. 최대중의 최소를 구하는 문제이므로 파라메트릭 서치를 생각해볼 수 있다.이 때 k를 mid값으로 정해놓은 뒤에 만족 여부를 확인하게 되는데만족여부는 dfs를 통하여 확인할 수 있다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546#include #include #include using namespace std;int n, a[555][555], b[555][555];int dx[] = .. 더보기
BOJ)5849 Cow Crossings 문제: icpc.me/5849N개의 2점이 주어진다.a[i]와 b[i]인데 이 문제는 각 (a[i],0)과 (b[i],1) 두 점을 잇는 N가지 직선들 중 다른 어떤 직선과도 겹치지 않는 직선의 수를 세는 문제이다.N^2으로 완전 탐색을 하는 방법으로는 해결이 불가능하니, 보통 이러한 류의 문제에서는 스위핑을 이용하게 되는데우선 a[i]를 기준으로 정렬을 해보자.그러고 a[i]가 증가하는 순서대로 보면 이러한 생각을 하게 될 수 있다.내가 이전에 본 직선들의 b[x]의 좌표 중에 나의 b[i]보다 하나라도 큰 수가 있다면 나는 이전에 업데이트 된 직선에 의해서 겹치는 직선이 된다는 걸 알 수 있다.이러한 원리로 우선 a[i]가 증가되는 순서로 안되는 직선들을 걸러준다.하지만 이렇게 처리하면 몇가지 직선이.. 더보기