문제 풀이
-
[프로그래머스] 단어 퍼즐문제 풀이 2020. 9. 23. 17:25
단어 퍼즐 문제) https://programmers.co.kr/learn/courses/30/lessons/12983 풀이)처음에 BFS를 이용해서 풀었으나 효율성을 통과하지 못했다. 효율성 통과 x 코드) 12345678910111213141516171819202122232425262728293031323334353637383940414243#include #include #include #include #include using namespace std; bool cmp(const string &a, const string &b) { return a.length() > b.length();} int solution(vector strs, string t){ int answer = 0; sort(st..
-
[백준] 2842번 집배원 한상덕문제 풀이 2020. 9. 18. 18:39
2842 집배원 한상덕 문제상덕이는 언덕 위에 있는 마을의 우체국에 직업을 얻었다. 마을은 N×N 행렬로 나타낼 수 있다. 행렬로 나뉘어진 각 지역은 우체국은 'P', 집은 'K', 목초지는 '.' 중 하나로 나타낼 수 있다. 또, 각 지역의 고도도 알고 있다.매일 아침 상덕이는 마을의 모든 집에 우편을 배달해야 한다. 배달은 마을에 하나밖에 없는 우체국 'P'가 있는 곳에서 시작한다. 상덕이는 현재 있는 칸과 수평, 수직, 대각선으로 인접한 칸으로 이동할 수 있다. 마지막 편지를 배달하고 난 이후에는 다시 우체국으로 돌아와야 한다.상덕이는 이렇게 매일 아침 배달을 하는 것이 얼마나 힘든지 궁금해졌다. 상덕이가 배달하면서 방문한 칸 중 가장 높은 곳과 낮은 곳의 고도 차이를 피로도라고 하자. 이때, 가장..
-
[백준] 4179번 불!문제 풀이 2020. 9. 17. 18:26
4179 불! 문제지훈이는 미로에서 일을 한다. 지훈이를 미로에서 탈출하도록 도와주자!미로에서의 지훈이의 위치와 불이 붙은 위치를 감안해서 지훈이가 불에 타기전에 탈출할 수 있는지의 여부, 그리고 얼마나 빨리 탈출할 수 있는지를 결정해야한다.지훈이와 불은 매 분마다 한칸씩 수평또는 수직으로(비스듬하게 이동하지 않는다) 이동한다. 불은 각 지점에서 네 방향으로 확산된다. 지훈이는 미로의 가장자리에 접한 공간에서 탈출할 수 있다. 지훈이와 불은 벽이 있는 공간은 통과하지 못한다. 입력입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다.다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문자들은 다음을 뜻..
-
[백준] 3967번 매직스타문제 풀이 2020. 9. 16. 19:50
3967 매직스타 문제매직 스타는 1부터 12까지 숫자가 헥사그램(hexagram)에 채워져 있는 모양으로 이루어져 있다.매직 스타의 이름에 매직이 들어가는 이유는 숫자 네 개로 이루어진 줄의 숫자를 모두 합하면 26이 되기 때문이다. 위의 그림의 여섯 줄에 쓰여 있는 숫자는 다음과 같다.1 + 4 + 10 + 1111 + 5 + 3 + 77 + 6 + 12 + 12 + 10 + 5 + 99 + 3 + 6 + 88 + 12 + 4 + 2매직 스타를 채우는 방법은 여러 가지가 있다. 일부만 채워진 매직 스타가 주어졌을 때, 수를 전부 다 채워서 매직 스타를 만드는 프로그램을 작성하시오. 입력매직 스타의 모양이 주어진다. 수가 채워져 있지 않은 곳은 x로, 채워져 있는 곳은 'A'부터 'L'까지 알파벳으로 ..
-
[백준] 9944번 NM보드 완주하기문제 풀이 2020. 9. 14. 17:23
9944번 N*M 보드 완주하기 문제) https://www.acmicpc.net/problem/9944 풀이)처음에 구조체 ball을 하나 만들어서, bfs로 구현 시도해보았는데 다시 방문한 곳을 방문처리하기가 까다로웠다. 처음 시도 방법)struct ball { int y, x, dir, cnt, change;ball() {}ball(int y,int x, int dir) {this->y = y; //y좌표this->x = x; //x좌표this->dir = dir; //공이 움직이는 방향this->cnt = 1; //공이 방문한 빈칸 개수this->change = 1; //공이 방향을 바꾼 횟수}}; bool visited[y][x][dir 0 ~ 4] 2번째 시도 방법)방문처리를 back trac..
-
[백준] 4196번 도미노문제 풀이 2020. 9. 11. 18:21
4196 도미노 문제도미노는 재밌다. 도미노 블록을 일렬로 길게 늘어세운 뒤 블록 하나를 넘어뜨리면 그 블록이 넘어지며 다음 블록을 넘어뜨리는 일이 반복되어 일렬로 늘어선 블록들을 연쇄적으로 모두 쓰러뜨릴 수 있다. 그러나, 가끔씩 도미노가 다른 블록을 넘어뜨리지 못하게 배치되어 있다면, 우리는 다음 블록을 수동으로 넘어뜨려야 한다.이제 각 도미노 블록의 배치가 주어졌을 때, 모든 블록을 넘어뜨리기 위해 손으로 넘어뜨려야 하는 블록 개수의 최솟값을 구하자. 입력첫 번째 줄에 테스트 케이스의 개수가 주어진다.각 테스트 케이스의 첫 번째 줄에는 두 정수 N, M이 주어지며 두 수는 100,000을 넘지 않는다. N은 도미노의 개수를, M은 관계의 개수를 나타낸다. 도미노 블록의 번호는 1과 N 사이의 정수다..
-
[백준] 4013번 ATM문제 풀이 2020. 9. 5. 19:32
4013 ATM 문제) https://www.acmicpc.net/problem/4013 풀이)SCC, dp를 이용해서 푸는 어려웠던 문제였다. 같은 간선을 여러번 사용할 수 있기 때문에,임의의 정점을 방문한다고 할때 그 정점이 속한 SCC내의 모든 정점을 방문해서 최대 현금을 구한다. 과정1. kosaraju algorithm을 이용해 SCC을 구한다. SCC를 구할때, 각 정점이 어떤 SCC에 속하는지 표시해준다 //int node[i] => i 번 정점이 속하는 SCC번호 각 정점이 속하는 SCC의 총 현금을 저장해준다 //int scc[i] => i 번 SCC의 총 현금, 즉 SCC에 속한 정점들의 현금 합 SCC 끼리 연결될 수 있다면, 그 연결 간선을 저장해준다 //vector adj_scc[..
-
[백준] 13511번 트리와 쿼리 2문제 풀이 2020. 9. 2. 01:15
13511 트리와 쿼리 2 문제N개의 정점으로 이루어진 트리(무방향 사이클이 없는 연결 그래프)가 있다. 정점은 1번부터 N번까지 번호가 매겨져 있고, 간선은 1번부터 N-1번까지 번호가 매겨져 있다.아래의 두 쿼리를 수행하는 프로그램을 작성하시오* 1 u v: u에서 v로 가는 경로의 비용을 출력한다.* 2 u v k: u에서 v로 가는 경로에 존재하는 정점 중에서 k번째 정점을 출력한다. k는 u에서 v로 가는 경로에 포함된 정점의 수보다 작거나 같다. 입력첫째 줄에 N (2 ≤ N ≤ 100,000)이 주어진다.둘째 줄부터 N-1개의 줄에는 i번 간선이 연결하는 두 정점 번호 u와 v와 간선의 비용 w가 주어진다.다음 줄에는 쿼리의 개수 M (1 ≤ M ≤ 100,000)이 주어진다.다음 M개의 줄..