그냥 블로그

https://www.acmicpc.net/problem/13459 13459번: 구슬 탈출첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B'www.acmicpc.net [문제 설명] 10*10 크기의 보드에 빨간 구슬, 파란 구슬, 통과할 구멍이 각각 1개씩 있다. 보드를 기울여서 구슬이 직선으로 움직이고 빨간 구슬이 10번 이내로 구멍을 통과하면 된다. 이때, 파란 구슬은 통과하면 안됨! [풀이 과정] 처음에 문제를 보고 완전 탐색, DFS를 떠올려서 그렇게 진행을 했다.... 근데 풀 수 없었음. 정확히 말하면, 처..

https://www.acmicpc.net/problem/1796 1796번: 신기한 키보드동혁이의 키보드에는 버튼 세 개와 LCD창 한 개가 달려 있다. LCD창에는 문자열 S가 쓰여 있다. 그리고 커서는 문자열의 가장 왼쪽 글자에 위치해 있다. 버튼 세 개는 왼쪽, 오른쪽, 엔터키이다. 왼www.acmicpc.net [...] 일단, 처음에 문제를 보면서 "타자 입력" "엔터나 오른쪽 왼쪽"을 보고 stack, bfs를 떠올렸다. 혹시 DP? 하기도 했는데 아니겠지하고 넘어감 ㅎㅎ.. 그리고 문제를 풀면서 풀이 방법에 근접한 방법을 생각해 냈는데 난독 이슈로 이상한 방법으로 풀이를 하다가 집어 던졌다... stack + 오른쪽 왼쪽 막 구현 하고 그런 거엿음 ㅋㅋㅋ 나중에 분류 표랑,, 스터디원 분이..

https://www.acmicpc.net/problem/16724 16724번: 피리 부는 사나이 첫 번째 줄에 지도의 행의 수를 나타내는 N(1 ≤ N ≤ 1,000)과 지도의 열의 수를 나타내는 M(1 ≤ M ≤ 1,000)이 주어진다. 두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열이 주 www.acmicpc.net [ 아이디어 구상 ] 일단 처음에 문제를 읽고 시뮬레이션이라고 생각했다. 말을 좀 어렵게 써놨는데 예시 그림?을 보면서 생각해보면 결국 구하는 것이 말이 'SAFE ZONE'이지 연결되지 않은 땅의 개수인 걸 알 수 있었다. 구하는 것 : 연결되지 않은 땅 개수 => BFS 아님 DFS로 구하면 되겠구나를 알 수 있었다. 그리고 방향으로 생각해 보면 연결되는 건..

1027번: 고층 건물 세준시에는 고층 빌딩이 많다. 세준시의 서민 김지민은 가장 많은 고층 빌딩이 보이는 고층 빌딩을 찾으려고 한다. 빌딩은 총 N개가 있는데, 빌딩은 선분으로 나타낸다. i번째 빌딩 (1부터 시작) www.acmicpc.net [문제] 요약하면, 빌딩들이 있고 그 빌딩에서 다른 빌딩이 보이는가 이다. (지붕을 이었을 때, 다른 빌딩으로 가로막혀 있거나 다른 빌딩이 선분 위의 점이면 안됨..) [문제 풀이] 문제를 보고 딱 떠오른게 기울기로 푸는 거다 문제의 조건인, "지붕을 이었을 때, 다른 빌딩에 닿으면 안된다" 라는 조건에서 각도를 생각할 수 있었는데, 해당 조건에 걸리지 않으려면 처음을 기준으로 쳤을 때 위의 그림처럼 앞선 빌딩들 보다 이루는 각이 크면 된다 ㅇㅇ 이건 작을 때도..

20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net [풀이 과정] 문제랑 입력을 보고 union find로 사이클 여부를 구해주는 문제라는 걸 알 수 있었다. 지난주에 kruskal 하면서도 썼던거라 빠르게 파악할 수 있었다. 1. 입력받으면서 싸이클 여부를 파악한다. 2. find_Cycle 함수에서 각 점의 루트 노드 값을 구해주고, 그 값을 기반으로 사이클이 돌고 있는지 확인해준다. 두 점의 루트 노드 값이 같다면 사이클이 돌고 있는 것이다. 사이클이 돌고 있지 않다면 값이 작은 쪽으로 루트 노드 값을 ..

1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net [문제] -풀이 시 고려한 조건- 1. 마을 내 모든 집들은 임의의 경로로 이어져 있어야 한다. (간선은 모두 양방향) 2. 가장 적은 유지비가 들어야 한다. 3. 최소 유지비를 제외한 모든 길을 제외할 수 있다. 4. N > N >> M; priority_queue q; vector branch(N+1); //유지비, 도착 점 for (int i = 0; i > A >>..