본문 바로가기
반응형

PS 문제 풀이/Jungol101

[Jungol] 정올 1840 치즈 출처: http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1113&sca=30 Input 13 12 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 1 1 0 0 0 1 1 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 1 1 1 1 1 0 1 1 0 0 0 0 1 1 1 1 0 0 1 1 0 0 0 0 0 1 1 0 0 0 1 1 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Out.. 2021. 2. 27.
[Jungol] 정올 1106 장기 출처: http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=386&sca=30 Input 9 9 3 5 2 8 Output 2 아래와 같이 말을 움직이면 2번에 졸을 잡을 수 있습니다. ① 말이 움직이는 방향은 8가지 입니다. ② visited[][] 배열을 초기에 임의의 큰 수로 초기화 한 후, BFS 탐색하면서 최소 움직임으로 방문한 횟수를 저장합니다. (즉, visited[][]에는 더 적은 움직임 횟수를 재방문 허용) ③ 졸이 위치한 좌표가 ex, ey일 때, visited[ex][ey] 출력 #include const int INF = 2e9; const int MAX_NM = 100 + 5; const int dx[] = {-2, -2, -1, -.. 2021. 2. 27.
[Jungol] 정올 1462 보물섬 출처: http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=734&sca=30 Input 5 7 WLLWWWL LLLWLLL LWLWLWW LWLWLLL WLLWLWW Output 8 - 육지가 바다로 나눠져 있다면 육지간 이동은 불가능합니다. - 연결된 육지에서 최단거리로 이동하되 가장 멀리 있는 곳의 거리를 찾는 문제입니다. → BFS - 육지(L)에 해당하는 모든 지점에서 이동할 수 있는 가장 먼거리를 찾습니다. (초기화 유의) 즉, 『L』로 표시된 모든 지점을 출발점으로 BFS 탐색하며 가장 멀리 도달한 거리를 찾습니다. - 특정 위치 (x, y)에서 출발 했을 때, visited[i][j] = (i, j)에 도달하기 위한 최단 거리 BFS 탐색이 끝.. 2021. 2. 27.
[Jungol] 정올 3008 교통수단 선택하기 출처: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=2281&sca=50&page=20 Input 4 6 99 2 1 2 3 1 3 4 1 4 7 2 3 3 2 4 5 3 4 2 2 3 30 10 3 200 1000 Output 3600 해당 문제는 BFS로 해결하는 문제로 중복 방문 확인을 visited[도시][남은 시간][교통수단] 3차원 배열을 이용합니다. ex) visited[x][y][z] = x 도시에 y초를 남기고 z 교통수단으로 방문 비용 → 동일한 조건으로 더 좋은 비용이 아닌한 중복 방문 허용 X - 차로 도착하는 경우에는 도착지에 렌트카 지점이 있어야 합니다. 즉, 도착지에 렌트카 지점이 있으면 렌트카 타고 왔어도 반납할 수.. 2021. 2. 27.
[Jungol] 정올 3109 숫자 야구2 출처: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=2391&sca=50&page=21 [BOJ] 2503 숫자 야구 문제와 달리 비교되는 숫자가 주어지지 않습니다. [BOJ] 백준 2503 숫자 야구 출처: https://www.acmicpc.net/problem/2503 Input 4 123 1 1 356 1 0 327 2 0 489 0 1 Output 2 ▶ 완전탐색 접근 3자리의 숫자는 1~9까지의 서로 다른 숫자로 구성되어야 합니다. 따라서 123~999까지 숫.. zoosso.tistory.com ① "1234"를 query에 보내고 결과 확인 4 strike이면 게임 종료 그렇지 않다면 그 기록을 저장해 대전 기록으로 활용해야 합니.. 2021. 2. 27.
[Jungol] 정올 3031 인형정리 출처: [Jungol] 정올 3031 인형정리 Input 7 2 1 2 2 2 1 2 1 Output 2 먼저 놓여있는 인형의 종류는 2종류이고 왼쪽에서 오른쪽으로 1, 2, 2, 2, 1, 2, 1로 7개의 인형이 진열되어 있다. 같은 종류끼리 정렬하는데 꺼낸 인형의 개수를 최소화하려면 왼쪽에서 1 번째와 6 번째 인형을 꺼내 왼쪽에서 1 번째로 유형 2의 인형을 왼쪽에서 6 번째로 유형 1의 인형을 배치한다. 이 때 꺼낸 인형의 개수는 2 개이다. Input 12 4 1 3 2 4 2 1 2 3 1 1 3 4 Output 7 O (M! * N) DFS 탐색을 통해서 인형 종류의 순서를 결정합니다. M 종류의 인형을 종류별로 배치하는 경우의 수 = M! ex) 1, 2, 3 → [1 2 3], [1 3.. 2021. 2. 27.
[Jungol] 정올 2217 DNA 조합 출처: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1478&sca=3030 Input 4 GATTA TAGG ATCGA CGCAT Output 13 DNA 조각은 2 ≤ N ≤ 7개가 있고 각 조각의 길이는 1 ≤ L ≤ 7이다. N개의 DNA조각을 임의의 순서로 나열해 인접한 두 DNA 조각에서 앞쪽 조각의 오른쪽 끝부분이 뒤쪽 조각의 왼쪽 끝부분과 최대한 많이 일치하는 부분을 찾고, 중복되는 부분을 제거한 후 나머지 부분을 순서대로 모아 새로운 DNA 조합을 만든다. 예를들어 GATTA + TACA = GATTACA DFS를 이용한 백트래킹으로 두 문자열을 연결할 때 중복되는 문자의 개수를 구합니다. DNA 조각의 개수가 최대 7개이므로 .. 2021. 2. 27.
[Jungol] 정올 1180 Dessert 출처: http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=463&sca=9040 Input 7 Output 1 + 2 - 3 + 4 - 5 - 6 + 7 1 + 2 - 3 - 4 + 5 + 6 - 7 1 - 2 + 3 + 4 - 5 + 6 - 7 1 - 2 - 3 - 4 - 5 + 6 + 7 1 - 2 . 3 + 4 + 5 + 6 + 7 1 - 2 . 3 - 4 . 5 + 6 . 7 6 사전순으로 최대 20개까지 출력하는 것이므로, 1 ~ 20까지의 숫자 순서는 변화가 없습니다. 문제에서 주어진 연산도 "+", "-", "." 순으로 우선순위를 가집니다. → 수와 수 사이에 연산자의 개수는 N - 1 개 입니다. → 가능한 경우의 수는 3N-1 에 해당합니.. 2021. 2. 27.
[Jungol] 정올 1681 해밀턴 순환 회로 출처: http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=954&sca=3030 Input 5 0 14 4 10 20 14 0 7 8 7 4 5 0 7 16 11 7 9 0 2 18 7 17 4 0 Output 30 1→ 4 → 5 → 2 → 3 → 1 ▶ 10 + 2 + 7 + 7 +4 = 30 ① 1번을 출발지로 DFS 탐색 ② void DFS(int depth, int v, int cost) 인자: 현재 단계(경유한 곳의 개수), 현재 위치, 누적 비용 ③ 마지막 시험장에서 다시 집으로 돌아올 수 있어야 합니다. 따라서 마지막에 집으로 오는 비용도 고려해야 합니다. ※ 분기한정을 통해 시간 효율을 올릴 수 있습니다. #include const int .. 2021. 2. 27.
[Jungol] 정올 1013 Fivestar (Bitwise) Input 5 6 .*.... .***** .*.... *****. .*.... Output 3 출처: 정올 Jungol 1013 Fivestar 해당 포스팅은 Bitwise를 이용한 풀이 다른 방식 풀이: [Jungol] 1013 Fivestar [Jungol] 정올 1013 Fivestar 출처: http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=292&sca=50 Input 5 6 .*.... .***** .*.... *****. .*.... Output 3 가로로만 막대를 놓는 경우 그리디 알고리즘으로 쉽게 막대의 개수를 구.. zoosso.tistory.com #include int N, M, ans = 100; int row[11], column.. 2021. 2. 27.
반응형

티스토리툴바