백준

풀이 과정 해당 문제는 단순한 투 포인터 문제이다. 두 값의 합이 0과 가까운 쌍을 찾으면 끝이다. 1. 주어진 x 배열을 정렬시킨다. 2. 문제에서 수들의 합이 매우 크기 때문에 minV를 매우 큰 값으로 설정하였다. 3. 투 포인터를 사용하기 때문에 0번째 인덱스와 n-1 인덱스부터 시작한다. 4. 오른쪽 인덱스 s와 왼쪽 인덱스 e의 합을 m으로 지정한다. 5. 절댓값 m이 minV보다 작을 경우 minV를 m으로 업데이트해준다. ans를 현재 x [s], x [e]로 업데이트해준다. 6. minV이 0이면 반복문을 종료하고 현재 ans을 출력한다. 7. m 값이 0보다 작을 경우 오른쪽 인덱스를 증가시키고 반대일 경우 왼쪽 인덱스를 감소시킨다. 풀이 코드 n,*x= map(int,open(0).r..

풀이 과정 본 문제는 전형적인 BFS문제이다. 왜냐하면 연결되어 있는 방의 개수를 물어봤기 때문이다. 부가적으로 특이한 요소를 첨가하였다. 각 좌표들 간에 연결되었는지를 15 이하의 값으로 주어져있다. 0~15 (?) 문제에서 언급한 힌트대로 이 문제는 좌표 이동을 비트 마스킹을 해준다. 하지만 비트 마스킹이 익숙하지 않아서,,, 나는 문자열로 표시를 하였다. 물론 하는 방법은 비트 마스킹이랑 똑같다..! "0000" ~ "1111" 맨 왼쪽부터 서북 동남을 의미하고 1은 이동 불가(벽으로 연결)를 의미하고 0은 이동 가능을 의미한다. 1. m*n 만큼 반복문을 돌려서 해당 (i, j) 위치를 방문하지 않을 경우 BFS 탐색을 한다. 2. 현재 위치 값을 bin함수를 이용하여 이진수를 나타내고 크기를 4..

2212번: 센서 첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있 www.acmicpc.net 문제 설명은 밑에 링크를 타시고 보시면 됩니다. 😶‍🌫️ [Python][백준 2212][정렬][그리디] 센서 - 컴도리돌이 풀이과정 해당 문제는 좌표를 단순히 정렬시켜서 센서들 간의 거리를 저장하고 정렬하여 n-k까지 합을 구하면 된다. 여기서 n-k까지 합을 구하는 이유를 물어본다면,, 문제를 그리면서 푸는 것을 comdolidol-i.tistory.com import java.io.BufferedReader; import java...

풀이과정 해당 문제는 좌표를 단순히 정렬시켜서 센서들 간의 거리를 저장하고 정렬하여 n-k까지 합을 구하면 된다. 여기서 n-k까지 합을 구하는 이유를 물어본다면,, 문제를 그리면서 푸는 것을 추천한다. 🙄 1. 센서 위치를 정렬시킨다. 2. x의 0번째 인덱스부터 n-1 인덱스까지 다음 좌표까지의 거리를 저장한다. 3. 다음 좌표까지의 거리들을 정렬시킨다. 4. 정렬된 좌표 간의 거리 리스트에서 n-k까지 합을 구하여 출력한다. 풀이 코드 n,k,*x = map(int,open(0).read().split()) ;x.sort() print(sum(sorted([x[i+1] - x[i] for i in range(n-1)])[:n-k]))

풀이과정 해당 문제는 뭔가 일단 규칙성을 찾아야 하게끔 생겨 버렸다. 😶‍🌫️😶‍🌫️ 일단 n이 홀수이면 0인 거 알겠지만, n이 짝수일 때 규칙성을 찾는데 애를 먹었다. 일단 n이 2일 때는 3이다. 그다음 n이 4일 때는 11이다. 근데 여기서 n이 2일 때 경우의 수 각각 2,2이기 때문에 2 * 2에 새로운 모양 2개를 더해준 값이다. 그렇다면 일단 dp [2] * dp [2] + 2라고 표현할 수 있다. 그다음 n이 6일 때는 41이다. dp [4] * dp [2] + dp [2] * 2 + 2 그다음 n이 8일 때는 dp [6] * dp [2] + (dp [4] + dp [2] ) * 2 + 2 그다음 n이 10일 때는 dp [8] * dp [2] + (dp [6] + dp [4] + dp [..

풀이과정 해당 문제는 방문 표시만 제대로 하면 쉽게 해결할 수 있는 문제이다. 물론 방문 표시가 생각보다 까다롭다. 😂 시작점에서 끝점까지 도달하는 최단 거리는 너비 우선 탐색(BFS)으로 구현하면 된다. 그렇다면 이 문제의 핵심은 방문 표시이다. 탈출을 하기 위해서는 '.' 공간만 이용할 수 있다. 물론 주어진 n*m 행렬 맵에서는 키라는 특이한 요소를 첨가했다. 키의 종류는 a, b, c, d, e, f 총 6가지이며, 키의 종류 따른 문의 종류도 A, B, C, D, E, F 총 6가지이다. 문제에서는 탈출구까지 가는 길에 문이 있으면 해당 문에 맞는 키 값을 소유하고 있어야 한다. 그렇기 때문에 BFS 탐색할 때 방문 표시를 가지고 있는 키 값들에 따라 해주어야 한다. 키의 종류는 총 6가지이다...

19641번: 중첩 집합 모델 S번 노드가 루트 노드일 때, 번호가 가장 낮은 노드부터 오름차순으로 방문해서 중첩 집합을 구성했을 때, 각 노드의 번호 left 필드와 right 필드를 출력한다. 총 N개의 줄에 걸쳐 i번째 줄에 i번 www.acmicpc.net 풀이 과정 만약 문제가 잘 이해 안 된다면 표를 잘 보시면 됩니다. 😊 표의 예시에서 "HI-ARC"가 root 노드로 시작됩니다. 그러기 때문에 root 노드 "HI-ARC"의 왼쪽 노드는 order을 1로 가집니다. 그 이후에 "HI-ARC"와 연결된 노드를 찾습니다. 표에서는 "경영 지원실"이 제일 빠른 노드입니다. 해당 "경영 지원실"의 왼쪽 노드는 다음 order인 2를 가집니다. "경영 지원실"과 연결된 노드... 노드... 연결된 ..

t or reversed_front > h : continue if t - reversed_back + reversed_front in visited : continue visited[t-reversed_back+reversed_front] = True q.append([t-reversed_back+reversed_front,depth+1]) else : print(-1)