백준32 BOJ 16234 - 인구 이동(Java) https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 풀이 인구이동이 더 이상 불가능 할때 까지 계속해서 이동 반복 이동되는 구역을 visit[][]로 확인, 다시 탐색하지 않도록 예외 처리 - 인구 이동이 가능한지 확인 - 인구 이동이 가능하다면 해당 구역 전체 인구 이동 - bfs를 이용하여 인근 구역 탐색 -> L < abs( map[y][x]-map[ny][nx] ) < R이라면 이동 가능 - 인구이동 구역 설정까지 bfs 탐색.. 2021. 12. 14. BOJ 11000 - 강의실 배정(Java) https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si 현재 탐색 요소의 강의 시작시간 -> 같은 강의실로 할당 불가능, 새로운 강의실 필요 import java.io.*; import java.util.*; public class Main { static.. 2021. 12. 7. BOJ 23290 - 마법사 상어와 복제(C++) https://www.acmicpc.net/problem/23290 23290번: 마법사 상어와 복제 첫째 줄에 물고기의 수 M, 상어가 마법을 연습한 횟수 S가 주어진다. 둘째 줄부터 M개의 줄에는 물고기의 정보 fx, fy, d가 주어진다. (fx, fy)는 물고기의 위치를 의미하고, d는 방향을 의미한다. 방향 www.acmicpc.net 풀이 한 위치에 물고기가 여러 마리일 수 도 있기 떄문에 vector fish[][]로 저장, 값은 물고기의 방향성 상어가 물고기를 먹었다면 냄새를 남기는 이차원 배열 smell[][]을 이용 smell[y][x]= 현재 연습 시점의 index을 남기고, 물고기가 이동할 때 이동 가능한지의 여부를 확인 할때, 현재 연습 시점 index - smell[y][x] 가.. 2021. 11. 27. BOJ 23288 - 주사위 굴리기2(C++) https://www.acmicpc.net/problem/23288 23288번: 주사위 굴리기 2 크기가 N×M인 지도가 존재한다. 지도의 오른쪽은 동쪽, 위쪽은 북쪽이다. 지도의 좌표는 (r, c)로 나타내며, r는 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로부터 떨어진 칸의 개수이다. 가장 왼 www.acmicpc.net 풀이 주사위 배열에 주사위 위치의 값 저장, 주사위 이동 시 배열 갱신 이동방향 dir[]={동, 남, 서, 북} 반복횟수 K만큼 진행 1. 주사위가 이동 방향으로 한칸 굴러감(굴러간 위치가 범위 밖이라면 반대방향으로 계산) - 주사위의 이동방향에 따라 주사위 배열의 값 수정 2. 주사위의 위치 (y, x)에 대해 점수 계산 - 동서남북 방향으로 연속해서 이동할 수 있는(BFS).. 2021. 11. 25. BOJ 20165 - 인내의 도미노 장인 호석(C++) https://www.acmicpc.net/problem/20165 20165번: 인내의 도미노 장인 호석 사람을 화나게 하는 법은 다양하다. 그 중에서도 악질은 바로 열심히 세워놓은 도미노를 넘어뜨리는 것이다. 이번에 출시된 보드 게임인 "너 죽고 나 살자 게임"은 바로 이 점을 이용해서 2명이 www.acmicpc.net 풀이 라운드만큼 반복, 한 라운드에 공격과 수비 순으로 동작 원래 상태 복구를 위해 원본 배열 보관 originp[][] 라운드가 지속되면서 변경되는 배열 map[][]을 갱신하며 진행 1. 공격 1-1. y, x, dir이 주어짐, cnt=map[y][x]-1, res=1 1-2. cnt가 0보다 큰 동안 반복 1-3. dir에 따라 y, x값 변경(한 칸 이동) -> y, x값이.. 2021. 10. 28. BOJ 1655 - 가운데를 말해요(C++) https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 풀이 우선순위 큐와 구역을 나누는 것으로 해결가능 - 중간 값과 더 작은 값들을 저장하는 오름차순 우선 순위 큐 : little_pq, - 중간 값보다 쿤 값들을 저장하는 내림차순 우선순위 큐 : big_pq 1. 상황에 따라 하나의 우선 순위 큐에 값을 저장 두개의 큐에 값이 없는 초기 상태거나 큐의 사이즈가 같다면 little_pq에 저장 외친 수(현재까지의 수)가 짝수라면 중.. 2021. 10. 22. BOJ 8090 - 택배(C++) https://www.acmicpc.net/problem/8980 8980번: 택배 입력의 첫 줄은 마을 수 N과 트럭의 용량 C가 빈칸을 사이에 두고 주어진다. N은 2이상 2,000이하 정수이고, C는 1이상 10,000이하 정수이다. 다음 줄에, 보내는 박스 정보의 개수 M이 주어진다. M은 1이 www.acmicpc.net 풀이 입력 값에 대한 정렬이 필요 1. 도착지 오름차순, 2. 출발지 오름차순 해당 지역을 거치는 택배의 총 개수를 저장하는 배열이 필요 -> int capacity[] * 단 트럭의 용량을 초과할 수는 없음 1. 정렬된 배송정보에 대한 탐색 2. 출발지 ~ 도착지중 지역을 거쳐가는 최대의 갯수 max_cnt를 저장 3. 현재 배송지에 대해 가져갈수 있는 택배의 개수를 구함 -.. 2021. 10. 19. BOJ 14888 - 연산자 끼워넣기(C++) https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 풀이 연산자마다 가능한 수가 정해져있음 -> 해당 연산자 개수와 숫자 개수(N)의 모든 경우의 수 탐색(브루트 포스) 1. 연산 순서 백터의 크기가 N-1보다 작으면 현재 사용가능한 연산자중에서 하나를 연산순서에 push, 연산 순서 백터의 크기가 N-1과 같다면 2로 이동 * 계산할 수가 N개라면 연산자의 개수는 N-1 2. 해당 연산자 순.. 2021. 10. 16. BOJ 2110 - 공유기 설치(C++) https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 풀이 두 공유기 사이의 거리에 대해 이분탐색을 이용 초기 값 -> left = 1, right = 공유기의 최대 좌표 1. mid = (left + right)/2 mid)로 했었는데 테스트 결과가 실패했음 문제에서의 거리는 공유기가 설치된 좌표까지 포함하는 거 였음 if(arr[i] - before >= mid) ex) 1, 3, 4 이고 거리.. 2021. 10. 14. 이전 1 2 3 4 다음
