늒네 기록

9849번: Rect (acmicpc.net) 좌표 평면의 축에 평행한 변을 가진 직사각형이 여럿 주어졌을때, 이 직사각형들의 공통 영역의 넓이를 구하는 문제. 아이디어는 다음과 같다.직사각형이 2개 있다면 두 직사각형의 공통 영역을 구하면 된다.3개 있다면 첫 2개의 공통 영역도 직사각형이므로, 이 직사각형과 세 번째 직사각형의 공통 영역을 구하면 된다.4개 있다면 첫 3개의 공통 영역이 직사각형이므로, ...그러니까, n개의 직사각형이 있으면 앞에 있는 직사각형부터 시작해서 공통영역을 계속 찾아나가면 된다.그렇다면 공통 영역은 어떻게 찾을까?공통 영역의 x좌표 중 작은 값은 첫 번째 직사각형의 최소 x좌표와 두 번째 직사각형의 최소 x좌표 중 큰 값이다.공통 영역의 x좌표 중 큰 값은 첫 번째 직사각..

10451번: 순열 사이클 (acmicpc.net) 아래의 문제와 동일한 아이디어로 풀린다.[BOJ-JS] 17848번 - Flight Turbulence (tistory.com) [BOJ-JS] 17848번 - Flight Turbulence17848번: Flight Turbulence (acmicpc.net) 문제를 이해해보자면 다음과 같다.n명의 사람이 자리에 앉아있음. 그런데 원래 앉아야 하는 자리가 아닌 곳에 앉아있을 수 있다.m번째 사람이 갑자기 본인 자리jaehaaheaj.tistory.com [n,...a]=(0+require('fs').readFileSync(0)).split``j=1while(n--){ c=[0,...a[j].split` `] r=0 for(p=1;p

4363번: Snow Clearing (acmicpc.net) 문제를 요약하자면 다음과 같다.도로망 주어짐. 첫 줄에 시작하는 위치, 그 다음줄부터 도로의 한쪽 끝부터 다른쪽 끝 위치, 즉, 엣지.도로망은 연결되어 있는 것이 보장된다.제설차로 이동하면서 모든 도로의 눈을 밀 것이다. 이때, 도로는 양방향으로 나있고(두 lane으로 이루어짐), 한 번 밀때 당연히 한 쪽만 밀린다.도로 위치의 단위는 미터다. 제설차는 처음 도로를 밀고 갈때 20km/h, 이미 밀고 지나간 도로는 50km/h로 움직인다.총 걸리는 시간을 출력하시오. 조건에는 나와있지 않지만, h:mm, 혹은 hh:mm 같은 포맷이 되어야 하는 것으로 보인다.아이디어는 다음과 같다.DFS를 한다고 생각하면 모든 lane을 한 번씩 돌면 된다...

5991번: Papaya Jungle (acmicpc.net) 문제를 이해해보자면,n by m 격자 칸에 파파야 열매가 있다. 좌측 상단이 (1,1), 우측 하단이 (n, m).(1,1)에 사람이 있다. 사람은 칸에 있는 파파야를 전부 먹어치운 다음 상, 하, 좌, 우로 움직일 수 있으며, 처음 주어진 격자 칸을 벗어날 수는 없다.움직일 수 있는 칸들 중 가장 많은 파파야가 있는 곳으로 이동하면서 (n, m)에 도착하면 멈춘다.이때 중요한 조건이 두 가지가 있는데,어느 순간에도 파파야가 가장 많은 칸은 유일하게 존재한다.어떤 테스트 케이스에서도 (n, m)에 도달할 수 있는 것이 보장된다.뒤의 두 조건이 더해지면서 매우 간단한 시뮬레이션 문제가 되었다![c,...b]=(0+require('fs').rea..

17848번: Flight Turbulence (acmicpc.net) 문제를 이해해보자면 다음과 같다.n명의 사람이 자리에 앉아있음. 그런데 원래 앉아야 하는 자리가 아닌 곳에 앉아있을 수 있다.m번째 사람이 갑자기 본인 자리에 앉고 싶어짐. 예를 들어, 원래 3번째 자리에 앉아야 하는 사람이 4번째 자리에 앉아있었다가, 원래 앉았어야 하는 자리로 가려고 한다.그래서 3번째 자리에 앉아있던 사람을 쫓아내고 앉아버린다. 그럼 이제 원래 3번째 자리에 앉아있던 사람이 원래 할당된 자리로 가야 한다.만약 3번째 사람의 원래 자리가 4번째 자리였다면 방금 4번 자리에서 사람이 온 것이니 비어있을 것이다. 그럼 그냥 가서 앉으면 된다.그게 아니라 3번째 사람의 원래 자리가 2번째 자리였다면, 또 앉아있는 사람을..

12852번: 1로 만들기 2 (acmicpc.net) 역으로 추적해나가는 방식으로 푼다. 코드를 짧게 줄이기 위해 오브젝트를 사용했는데, 배열로 풀어도 아이디어는 같다. 나는 오브젝트의 키값에 만들고자 하는 숫자를, 아이템에 해당 숫자에 도달한 경로를 배열로 넣어두었다.숫자 i를 만드는 방법은i가 2로 나뉠 경우 i/2를 만드는 경로에 i 추가.i가 3으로 나뉠 경우 i/3를 만드는 경로에 i 추가.i-1을 만드는 경로에 i 추가.위의 셋이 있는데, 이 중 제일 짧은 경로를 아무거나 하나 택해서 i를 만드는 경로로 사용하면 된다.위와 같은 방식으로 2, 3, ..., n을 만드는 경로를 전부 구하면 끝.n=+require('fs').readFileSync(0)d={1:[1]}i=1while(i++a.l..

17204번: 죽음의 게임 (acmicpc.net) 이 문제와 아이디어가 정확히 같은 문제다.[a,...b]=(0+require('fs').readFileSync(0)).split``;[n,m]=a.split` `i=0k=b[0]while(++i

15886번: 내 선물을 받아줘 2 (acmicpc.net)아이디어는 간단하다. 주어진 지도를 벗어나지 않으므로 문자열은 무조건 E로 시작하고 W로 끝나는 것이 보장되어 있고, E, W를 다음과 같이 화살표로 표시하면 같은 색으로 묶이는 곳의 방향 변경 지점 둘 중 한 곳 아무데나 선물을 놓을 경우 하나의 색을 커버 가능(그 색의 어디서 시작하든 선물을 가져갈 수 있음)하다는 것을 알 수 있다. EEEEEWWWEEEWEEEWWWW →→→→→←←←→→→←→→→←←←← 그리고 앞서 말한 방향 변경 지점은 'EW'로 찾을 수 있다. 즉, 문자열 전체 중 EW가 몇 번 나타나는지 세는 것으로 답을 찾을 수 있다.console.log((2+require('fs').readFileSync(0)).match(/EW/..

11558번: The Game of Death (acmicpc.net) 배열의 첫 번째 요소부터 시작해서, 해당 요소가 가리키고 있는 배열의 요소를 다시 얻어내고, ... 이걸 여러 번 반복해서 배열의 마지막 아이템에 도달할 수 있는지, 있다면 몇 번의 시행만에 도달할 수 있는지 출력하는 문제. 주요한 아이디어는 다음과 같다.- 첫 아이템부터 시작해서 시뮬레이션으로 풀면 된다. 다만 무한히 시행해도 마지막 아이템에 도달하지 못하는 경우가 있을 수 있다.- n개의 노드로 이루어진 그래프에서는 사이클의 크기가 이무리 커도 n을 넘지 못한다. 그렇기 때문에 시행을 n번 반복했음에도 불구하고 마지막 아이템에 도달하지 못했다면 영영 도달할 수 없다는 말이 된다. a=(0+require('fs').readFileS..

13450번: László Babai (acmicpc.net)문제 지문만 보면 길이도 길고 중간에 집합 관련 설명도 있어서 겁 먹기 딱 좋게 생겼지만, 사실은 매우 단순한 문제다.노드가 셋 있다. 각각 1, 2, 3 번호가 붙어있다.엣지는 0개 이상, 3개 이하 있다.첫 줄에는 테스트 케이스 개수가 주어져 있다.각 테스트 케이스는 두 개의 그래프 정보로 이루어져 있다.각 그래프 정보의 첫 줄에는 엣지 개수 m이 주어져 있고, 이후 m개의 줄에 각 엣지가 어떤 점으로 이루어져 있는지 정보가 주어져있다.두 그래프의 형태가 같으면 yes, 다르면 no 출력.아이디어도 매우 간단한데, 노드가 3개이므로 엣지 개수가 같으면 무조건 동형 그래프일 수밖에 없다. 이건 엣지 개수마다 케이스 나눠서 증명하면 매우 간단...