본문 바로가기

[PS] 문제풀이/백준39

[ 백준 9205 ] 맥주 마시면서 걸어가기 (C++) [문제보기] [해결과정] 1. 좌표를 저장할 배열 arr[MAX][2] 와 방문 체크할 배열 check[MAX] 준비 2. 집(0번 순서) 부터 편의점(1부터 N까지 순서), 마지막 도착지 (N+1번 순서) 까지 입력 받음 3. BFS() 3-1. 좌표의 절대값 (x 비교값 + y 비교값) 이 1000 이하여야 이동가능! [소스코드] 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 #include #include .. 2019. 12. 17.
[ 백준 1079 ] 마피아 (C++) [문제보기] [해결과정] 1. 총 4가지 입력 (1. 사람 수, 2. 사람 마다 각각의 점수, 3. 2차원 배열의 점수표, 4. 은진이 IDX) 2. DFS (브루트포스) 2-1. 기저조건 : 은진이가 죽거나, 남은 사람이 1명 일 때... 2-2. 현재 인원이 짝수일 경우 (밤) 2-2-1. 사람 수 만큼 for문을 돌며, 은진이거나 이미 죽은 사람 인덱스라면 continue; 2-2-2. 그렇지 않으면 해당 인덱스 사람을 죽이고, 나머지 살아있는 사람들의 점수를 변경 2-2-3. DFS 실행 (사람-1, 날짜+1) 2-2-4. 시행 후 위 과정을 반대로 시행 2-3. 현재 인원이 홀수일 경우 (낮) 2-3-1. 점수가 가장 높은 사람 찾기 2-3-2. 은진이가 가장 점수가 높을 경우 기저조건 시행 2.. 2019. 12. 11.
[ 백준 1113 ] 수영장 만들기 (C++) [문제보기] [해결과정] 1. 입력 받을 때 0,0 부터가 아닌 1,1 부터 2019. 12. 8.
[ 백준 1614 ] 영식이의 손가락 (C++) [문제보기] [해결과정] 아픈 손가락 별로 경우의 수가 어떻게 나오는지 규칙성 파악 1. 첫 번째 손가락 일 경우(엄지) : 0, 8, 16, 24, 32, 40, 48 ---> 8씩 증가 2. 두 번째 손가락 일 경우(검지) : 1, 7, 9, 15, 17, 23, 25 ---> 초기값 1 : 6 증가, 2 증가 반복 3. 세 번째 손가락 일 경우(중지) : 2, 6, 10, 14, 18, 22, 26 ---> 초기값 2 : 4씩 증가 4. 네 번째 손가락 일 경우(약지) : 3, 5, 11, 13, 19, 21, 29 ---> 초기값 3 : 2 증가, 6 증가 반복 5. 다섯 번째 손가락 일 경우(새끼) : 4, 12, 20, 28, 36, 44 ---> 초기값 4 : 8씩 증가 [소스코드] 1 2 .. 2019. 12. 4.
[ 백준 2733 ] Brain f*ck (C++) [문제보기] [해결과정] 1. 문자열 입력 받기 1-1. 공백 포함 : getline(cin, string변수명) 사용 1-2. 만약 입력 받은 문자열이 "end"면 종료 2. 문자열 공백 제거 2-1. 변수.erase(remove(변수.begin(), 변수.end(), ' '), 변수.end()); 3. 문자열에 %문자 뒷 부분 제거 3-1. 다른 string변수를 만들어 %문자 이전까지 문자들을 복사했음. 4. 스택 생성 4-1. 만약 '[' 문자가 있다면 스택에 해당 위치(idx)를 push 4-2. 만약 ']' 문자가 있다면 스택에서 top에 있는 idx위치를 받아 '[' 위치 즉 스택에 있던 idx와 ']' 위치 즉 현재 idx 값을 맵에 저장. 5. 스택이 비워있다면 정상적인 과정을 거쳐온 것.. 2019. 12. 3.
[ 백준 16496 ] 큰 수 만들기 (C++) [문제보기] [해결과정] 1. string 배열을 활용하여 입력 값을 받는다. 2. sort STL을 사용하여 sort 시킨다. sort 할 때 비교 함수 cmp 정의를 다음과 같이 한다. 2-1. sort할 string 변수 2개를 각 각 a와 b로 설정한다. 2-2. a+b 그리고 b+a를 하여 이 두개의 값을 비교한다. 2-3. a+b가 크다면 a를 앞에, b+a가 크다면 b를 앞에 배치시킨다. 3. 모두 0으로 입력 되있을 경우 예외처리로 flag 변수를 둔다. [소스코드] 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 .. 2019. 12. 3.
[ 백준 17822 ] 원판 돌리기 (C++) [문제보기] [해결과정] 구조체에 deque를 생성하여 원판 1개에 대해 deque를 적용했다. (이 방법은 처음 시도 해봤다. 다음엔 구조체 안에 큐와 스택, 배열등을 넣어 고차원 배열을 생성하는데 주로 사용해봐야겠다.) 1. 원판 입력 받기 - 구조체[원판번호].dq.push_back(번호) 를 활용하여 원판에 대한 정보를 입력받음 2. 원판 돌리기 - 원판 돌리기 할 때 주의 할 점은, 입력 받은 x값의 배수에 해당하는 원판은 모두 돌려줘야한다. 그래서 반복문을 만들어 주고, x값의 배수가 n값 보다 커지면 빠져나오는 식으로 작성했다. - 원판 돌리기 turn 함수를 만들어 돌렸다. - turn 함수의 경우 deque로 원판을 만들었기에, 시계방향 및 시계반대방향으로 돌리는 것은 크게 어렵지 않았다.. 2019. 12. 2.
[ 백준 17836 ] 공주님을 구해라! (C++) [문제보기] [해결과정] 1. 맵 저장 배열(2차원), 방문 체크 배열(3차원), 구조체(y좌표, x좌표, 방문시간, 검획득여부) 큐 생성 2. (0,0)부터 BFS 탐색 시작 2-1. 만약 방문 좌표가 검이 있는 곳이면, 다음 방문확인은 check[y][x][1] 에서 확인. 2-2. 아직 검을 찾지 못했다면, 다음 방문확인은 check[y][x][0] 에서 확인. 3. 공주님을 찾으면 시간 값을 저장하고 return; 위 사진과 같이 검을 안먹었을 때는 check[y][x][0]에서 BFS탐색을 계속하고, 만약 검을 먹었을 경우는 check[y][x][1]에서 검 먹기전 시간을 이어 탐색을 한다. 이때, 검을 먹었을 경우에는 벽을 모두 부술 수 있으니, map 체크를 하지 않아도 된다. (우측 사진처.. 2019. 11. 29.
[ 백준 17779 ] 게리맨더링2 (C++) [문제보기] [해결과정] 1. 기준점 (y,x)를 잡고 기준점으로 부터 왼쪽아래 대각선 (d1)과 오른쪽아래 대각선 (d2)가 갈 수 있는 최대 범위를 완전 탐색 2. 위쪽, 왼쪽, 오른쪽, 아래쪽 점 4개의 좌표 변수를 생성한다. (ty, tx, ly, lx, ry, rx, by, bx) 2-1. 위쪽 좌표는 1번에서의 기준점 (y,x) 2-2. 왼쪽 좌표는 기준점 (y,x)에서 d1만큼 이동한 좌표 ---> ( (y +dy[0] * d1), (x +dx[0] * d1) ) 2-3. 아래쪽 좌표는 왼쪽 좌표 (ly, lx)에서 d2만큼 이동한 좌표 ---> ( (ly + dy[1] * d2), (ly + dy[1] * d2) ) 2-4. 오른쪽 좌표는 기준점 (y,x)에서 d2만큼 이동한 좌표 --->.. 2019. 11. 28.

티스토리툴바