본문 바로가기

[PS] 문제풀이/백준39

[ 백준 17471 ] 게리맨더링 (C++) [문제보기] [해결과정] 1. input : n, arr (int형) 배열에 각각의 인원수 담기 -> 2차원 vector에 각각의 점에 간선 긋기 2. dfs(int count, int r(레드갯수), int b(블루갯수)) -> count != n+1 이라면, color에 색칠 후에 dfs(count+1, 색칠한곳+1, 색칠안한곳) 전송 -> count == n+1 이라면 아래 3번 수행 3. function -> red, blue 각각의 진영 갯수 0으로 초기화 -> redSum, blueSum 각각의 총합 0으로 초기화 -> 방문 체크 배열(check) 초기화 -> rf, bf 플래그 초기화 -> 1~N까지 점을 돌며, 레드 진영 한번, 블루 진영 한번.. 각각 한번씩 정점을 큐에 넣고 그 색에 대.. 2020. 2. 27.
[ 백준 1712 ] 손익분기점 (C++) [문제보기] [해결과정] 1. input : long long int 타입으로 a, b, c 입력 2. a + bx > cx 를 찾기 -> 예외 처리 b>=c 인 경우... [소스코드] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 /* BOJ 1712 - 손익분기점 Created by haejun on 2020/02/27 */ #include #include #include #include #include #include using namespace std; #define ll long long int ll a, b, c; int main(){ ios_base::sync_with_stdio(0); cin... 2020. 2. 27.
[ 백준 1405 ] 미친 로봇 (C++) [문제보기] [해결과정] 1. input : n, double 형 d[4] ( 동, 서, 남, 북 ) -> d[i]/=100으로 해서 소수점으로 변환 2. 동, 서, 남, 북으로 이동하는 것을 맵에서 check 하기 위해서 map배열을 만들어준다. -> 맵의 가장 중앙 지점을 방문 처리 한다. 3. 맵의 가장 중앙 지점 부터 dfs 실행 -> dfs(y,x, cnt, p) cnt는 dfs count이고, p는 확률(소수)를 담을 변수 -> 만약, 단순한 경로(겹치지 않는 경로) 일 경우 ret += p -> 현재까지의 확률을 정답란에 저장 -> 만약, 단순한 경로가 아닌 경우(이미 방문한 지점을 방문) 패스 4. output : 소수점 11자리 까지 지정하여 출력 -> cout.precision(11);.. 2020. 2. 26.
[ 백준 3197 ] 백조의 호수 (C++) [문제보기] [해결과정] 1. 입력 받기 (n, m , arr[][]) -> 백조 구조체를 생성하여, 0번 백조 1번 백조 입력 받기. -> 물일 경우 ( . ) wq(큐)에 넣기 2. q(큐)에 0번 백조 좌표 넣기 3. 결과를 도출할 날짜 ans =0으로 셋팅 후 무한 반복문 실행 4. nq( q와 동일한 큐 )생성 5. 0번 백조 돌리기 (q를 다 돌때까지) -> 만약 X라면 nq에 좌표 넣기 -> 만약 X가 아니라면 q에 좌표 넣기 ★★★0번 백조가 돌아다닐 수 있는 범위를 탐색하는 것임! 6. q에 nq를 넣기 7. 얼음 부수기 -> int s 에 wq.size() 값 대입 -> while(s--) 반복문 BFS 실행 -> 만약 X라면 wq에 좌표 넣고 해당 좌표 값을 '.'으로 변경 ★★★ 여.. 2020. 2. 26.
[ 백준 2146 ] 다리 만들기 (C++) [문제보기] [해결과정] 1. 입력 받기 (n, arr[][]) 2. 섬 번호 메기기 -> group 변수 선언 (섬 번호 Count) -> arr 배열을 돌면서, 1이면서 방문하지 않은 곳이라면 q(큐)에 좌표 넣기 -> 해당 좌표에 map배열에 gNum 입력과 방문체크 후 BFS() 실행 ★★★ 여기서 섬들의 좌표가 잘 찍혔는지 map을 print 해서 디버깅 한번 해보기!!! 3. 반복문을 사용해 섬번호 1번부터 끝번호까지 탐색 -> check배열 초기화 -> func(섬번호) 함수 실행 4. func(섬번호) 함수 -> arr 맵을 돌며 섬번호와 같은 좌표는 q2( y좌표, x좌표, cnt(초기값0) ) 삽입 -> q2에 대한 bfs 실시 -> 만약 다음 노드가 방문하지 않은 곳이고, 맵에서 0 .. 2020. 2. 26.
[ 백준 1926 ] 그림 (C++) [문제보기] [해결과정] 1. input -> n, m (세로, 가로) 변수, arr (map 2차원 배열) 2. arr 맵을 돌며, arr[i][j]==1 이고, check[i][j]==0 (방문하지않음) 이라면, 진입 -> group(집합 갯수)를 +1 시키고, cnt(원소 갯수)를 1로 초기화한다. -> ★★★그리고 만약 maxCnt(최대 원소 갯수) 보다 cnt가 크면 maxCnt == cnt; -> check[i][j]==1로 방문체크를 한다. -> queue에 i,j좌표를 삽입하고, BFS()로 진입한다. 3. BFS -> 주변 4방향을 탐색하며, arr[i][j]==1이고, check[i][j]==0 인 곳 진입 -> cnt(원소 갯수)++; -> 그리고 만약 maxCnt(최대 원소 갯수) .. 2020. 2. 24.
[ 백준 17472 ] 다리 만들기2 (C++) [문제보기] [해결과정] 1. 입력 받기 (n, m, arr[][]) 2. 섬 번호 메기기 -> gNum 변수 선언 (섬 번호 Count) -> arr 배열을 돌면서, 1이면서 방문하지 않은 곳이라면 q(큐)에 좌표 넣기 -> bq(또 다른 큐)는 추후 해당 좌표가 다른 섬이랑 연결 될 수 있는지 확인 하기 위한 것 -> 해당 좌표에 map배열에 gNum 입력과 방문체크 후 BFS() 실행 -> 해당 좌표에서 상,하,좌,우에 1이 있다면 방문체크 후, q(큐), bq(큐)에 넣기. -> 다음 좌표의 map에는 gNum(섬 번호) 입력. ★★★ 여기서 섬들의 좌표가 잘 찍혔는지 map을 print 해서 디버깅 한번 해보기!!! 3. 2번 과정에서 bq(큐)에 넣은 값들을 하나씩 꺼내보며, 다른 섬으로 갈 .. 2020. 2. 22.
[ 백준 17822 ] 원판 돌리기 (C++) [문제보기] [해결과정] 1. deque 2차원 배열 생성. 2. deque에 값 넣기. 3. 문제 입력 받기 (돌릴 내용) 4. turn 함수 실행 전, x의 배수 만큼 돌릴 수 있도록 반복문 설정 후 turn 진입 - 만약 시계 방향이라면, 뒤에 것을 앞으로... - 만약 반시계 방향이라면, 앞에 것을 뒤로... 5. 같은 숫자 지우기 - 절대값으로 비교 ! 좌우, 앞뒤, *** 가장 중요한 맨앞, 맨뒤 *** ---> 같은 수라면 음수로 설정 - 절대값으로 비교하는 이유 : 이미 발견된 수가 있을 수 있으므로... - 만약 같은 숫자를 단 한번이라도 지운 적이 있다면 flag 변수 설정 - 모든 작업 후에, 음수인 숫자를 0으로 변경 6. 만약 같은 숫자가 하나도 없었더라면, - deque에 있는 .. 2020. 2. 19.
[ 백준 16234 ] 인구 이동 (C++) [문제보기] [해결과정] 1. - int형 arr배열, int형 check배열 선언 - int cnt (나라 합), int sum (나라의 값들을 합한 값), int checkCnt (check배열에 같은 수가 저장되어 있으면 서로 동맹), bool flag (변화가 있는지 없는지, 변화가 없다면 전체 STOP) 2. n, L, R, arr 입력 3. while 반복문 실행 - 방문체크 초기화, checkCnt (=1) 초기화, flag (=true) 초기화 - arr 배열 전체 순회하면서 방문하지 않았다면 queue에 삽입 - BFS 실행하며 인원조건이 맞는지 확인, 인원조건이 맞다면 check[i][j] = checkCnt 하고 queue에 삽입, 그리고 cnt++(나라 합) 해주고 sum+=arr[.. 2020. 2. 12.
[ 백준 1238 ] 파티 (C++) [문제보기] [해결과정] 1. 2차원 배열 초기값을 -1로 셋팅 2. input : v[a][b] = c ---> a에서 b까지 가는데 c시간이 걸린다. 3. 2차원 배열을 순회하며 -1인 값을 987987987(최대 값)으로 변경 4. 플로이드 와샬 알고리즘 실행 5. 모든 노드에 대한 탐색을 실행 -> i에서 x까지의 거리, x에서 i까지의 거리를 합하고 ans와 비교하여 큰 값 갱신 [소스코드] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 6.. 2020. 2. 12.
[ 백준 1920 ] 수 찾기 (C++) [문제보기] [해결과정] 1. 수 입력 받기. 2. 오름차순 정렬 (sort) 3. 문제 입력 받기 ( 입력 받고 바로 결과 값 도출) 4. 이분 탐색 활용 5. 이분 탐색은 값을 기준이 아닌 배열의 idx 값을 기준으로 이분 탐색 시행 [소스코드] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 #include #include #include #include #include #include #include using namespace.. 2020. 2. 3.
[ 백준 1759 ] 암호 만들기 (C++) [문제보기] [해결과정] 1. int 배열 생성 2. char 변수로 문자들 입력 받고 ( 변수 - 'a' ) 2020. 2. 3.
[ 백준 15686 ] 치킨 배달 (C++) [문제보기] [해결과정] 1. (Y,X)를 저장할 수 있는 구조체를 생성 2. 구조체를 담는 집 배열, 치킨 배열을 생성 3. 각각의 배열에 카운트를 해주는 집 Cnt, 치킨 Cnt 변수 생성 4. 입력 받기 5. 조합(dfs)으로 치킨 집 m개 만큼 뽑기 6. dfs 기저조건에서 모든 집에 대해, 뽑힌 치킨집과의 가장 짧은 거리를 저장 [소스코드] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 .. 2020. 2. 3.
[ 백준 16235 ] 나무 재테크 (C++) [문제보기] [해결과정] 1. 2차원 vector로 맵 구현 (arr), 현재 양분 상태 저장 맵(map), S2D2 기계가 추가할 양분 맵 (mapS) 구현 2. 양분 상태의 초기값은 5, S2D2 양분 입력받기 3. 나무 입력받기 (y, x, age) 순으로... 4. 봄, 여름, 가을, 겨울 구현하기 (봄과 여름은 함께 구현) - 봄, 여름 : arr[i][j].size() 가 0이 아니라면, 나무가 있는 상태 이므로 접근, arr vector를 오름차순으로 정렬 후 임시 vector를 하나 만들어주고, 현재 나무의 나이와 양분 상태를 체크하여 양분이 충분하다면 양분 맵은 나무의 나이만큼 줄여주고, 임시 vector에 추가. 만약 나이만큼 되지 않는다면 death 변수에 나무의 나이/2 만큼 더함... 2020. 1. 31.
[ 백준 17825 ] 주사위 윷놀이 (C++) [문제보기] [해결과정] 1. 윷놀이 판을 구현 (map 초기화/설정) -> 해당 노드에 다음 이동할 노드 번호를 저장 (map 배열) -> 방향 전환이 되는 노드를 따로 관리 (turn 배열) -> 각각의 노드의 점수를 관리 (score 배열) -> 해당 노드에 말이 있는지 없는지 확인 배열 (check 배열) 2. 주사위는 무조건 10번 던지니까, 10번 횟수 기록 (arr 배열) 3. 말은 총 4마리로 움직임 -> 순열 구현 ( 각각의 주사위로 인하여 어떤 말을 움직일지 모르니 완전 탐색 DFS 구현) 4. 말의 움직임 -> 현재 말의 위치, 말이 도착할 위치, 주사위의 갯수 총 3개의 변수 필요 -> 예외 처리 : 만약 현재 위치가 변환점이라면, turn 배열을 이용하여 위치 변환 : 만약 도착 .. 2020. 1. 28.

티스토리툴바