Problem solving/BOJ29 [BOJ] 1149. RGB거리 (C++) 문제 1번 집부터 N번 집이 순서대로 있다. 집은 RGB 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 최솟값은? 1번 집의 색은 2번 집의 색과 같지 않아야 한다. N번 집의 색은 N-1번 집의 색과 같지 않아야 한다. i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다. 생각할 것 3가지 조건을 모두 반영해보자 표를 만들어서 풀었다 집 번호 / RGB R G B 0 26 40 83 1 40(0번집 G) + 49(1번집 R) = 89, 83(0번집 B) + 49(1번집 R) = 132 따라서 89 기록 26 + 60, 83 + 60 => 86 26 + 57, 40 + 57 =>.. 2023. 8. 8. [BOJ] 5427. 불 (C++) 문제 건물의 일부에 불이 났고, 불은 매 초마다 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 상근이는 동서남북 인접한 칸으로 이동할 수 있으며 1초가 걸린다. 벽을 통과할 수 없고, 불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동할 수 없다. 얼마나 빨리 빌딩을 탈출할 수 있는지 구하기. 탈출할 수 없는 경우 IMPOSSIBLE 출력 생각할 것 1초마다 인접한 방향으로 퍼져나가므로 BFS를 사용하자. 반례 1) 1 5 6 *#.## #...# #...# #...# #.@.# ##### 답 : 5 아래의 조건을 잘 정의해주어야 한다. 벽이 아니고, 방문하지 않았고, 불이 없거나 불이 아직 퍼지기 전인 경우(도망칠 수 있는 경우) if (board[nx][ny] != '#' && run[nx][n.. 2023. 8. 8. [BOJ] 2630. 색종이 만들기 (C++) 문제 전체 종이가 모두 같은 색으로 칠해져 있지 않으면 가로와 세로로 중간 부분을 잘라서 똑같은 크기의 네 개의 N/2 × N/2색종이로 나눈다. 이때도 모두 같은 색으로 칠해져 있지 않으면 같은 방법으로 나눈다. 이와 같은 과정을 잘라진 종이가 모두 하얀색 또는 파란색으로 칠해져 있거나 하나의 정사각형 칸이 되어 더 이상 자를 수 없을 때까지 반복한다. 생각할 것 같은 동작을 반복하므로 재귀함수를 사용하고 같은 크기 4개로 나누는 동작을 분할 정복을 활용해보자 코드 #include #include using namespace std; int blue = 0; int white = 0; bool confirm(vector &board, int sx, int sy, int size) { // 모두 같은 색.. 2023. 8. 8. [BOJ] 14426. 접두사 찾기 (C++) 문제 입력으로 주어지는 M개 문자열 중 집합 S에 포함되어 있는 문자열 중 적어도 하나의 접두사인 것의 개수 구하기 생각할 것 문자를 앞에서부터 순차적으로 검색해서 존재여부를 판단하므로 트라이를 사용해보자 코드 #include #include using namespace std; struct Trie { Trie *node[26]; Trie() { for (int i = 0; i < 26; i++) node[i] = NULL; } ~Trie() { for (int i = 0; i < 26; i++) { if (node[i]) { delete node[i]; } } } void insert(string &str, int idx) { if (idx == str.size()) return; // 문자열 끝까지.. 2023. 8. 7. 이전 1 2 3 4 5 6 ··· 8 다음