본문 바로가기

[PS] 문제풀이47

[ 백준 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.
[ 백준 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.
[ SWEA 7829 ] 보물왕 태혁 (D4) (C++) [문제보기] [해결과정] 1. 약수 들을 배열에 입력받고 오름차순으로 정렬 (sort 사용) 2. 만약 약수의 갯수가 1개면 답은 arr[처음] * arr[처음] 그렇지 않으면 답은 arr[처음] * arr[끝] [소스코드] 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 #include #include using namespace std; int arr[1000]; int main() { int t; cin >> t; for (int o = 1; o > p; for (int i = 0; i > arr[i]; } if (p == 1) ans = arr[0] * arr[0]; else { sort(a.. 2019. 12. 1.