Deff_Dev

문제 이 문제는 제목 그대로 물건을 3개 샀을 때, 해당 묶음에서 가장 싼 제품을 무료로 줄 때, 최소 비용을 출력하는 문제이다.풀이최소 비용을 만들기 위해서는 가장 비싼 제품을 무료로 받으면 된다. 가장 비싼 제품을 무료로 받기 위해서는 내림차순 정렬을 이용하여 3개씩 구매하면 무료로 받을 수 있는 가장 비싼 제품들을 고를 수 있다.#include using namespace std;bool cmp (int a, int b){ return a > b;}int main(){ ios_base::sync_with_stdio(0); cin.tie(0); int n; cin >> n; vector v(n); for (int i = 0; i > v[i]; } sort(v.begin(), v.end(), cmp);..

문제 자연수 A를 B번 곱한 수를 C로 나눈 나머지 값을 구하는 문제이다.풀이최대 연산 횟수는 약 21억이기 때문에, B번을 다 곱하면 시간 초과가 나온다. 그렇기 때문에 분할 정복을 이용해서 풀이해야한다. 예를들어서 입력이 2 8 5 일 때, 2를 8번 곱해서 256이 나오고 5를 나눈 나머지인 1이 출력될 것 이다.2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 = 256 하지만 이 연산에도 규칙이 있다. (((2^2)^2)^2)처럼 제곱을 이용하면 8번해야하는 연산을 3번으로 줄일 수 있다. 왜 그럴까 ? 위 식을 계산해보면 아래와 같다.2^2 = 44^2 = 1616^2 = 256 이 규칙을 적용해서 문제를 풀어봤다.#include using namespace std;long long a, ..

문제이 문제는 (0,0) 에서 (n -1 , m - 1) 위치로 가야할 때, 단 한 번 벽을 뚫고 갈 수 있다.이때, 최단 거리를 출력하는 문제이다.풀이BFS를 이용하여 해당 문제를 풀이했다. 3차원 배열을 이용하여 [y 축][x 축][벽 파괴 유무]로 맵을 만들었다. 이를 BFS를 이용하여 (n - 1, m - 1)까지의 최단거리를 구했다.#include using namespace std;int arr[1000][1000][2];int dx[4] = {0, 0, 1, -1};int dy[4] = {1, -1, 0, 0};int n, m;int BFS(){ queue, int>> q; q.push({{0, 0}, 0}); arr[0][0][0] = arr[0][0][1] = 1; while(!q.em..

문제 w * h 크기의 건물에 불이 났을 때, 상근이가 얼마나 빨리 탈출할 수 있는지 출력하는 문제이다. 입력'.': 빈 공간'#': 벽'@': 상근이의 시작 위치'*': 불풀이입력을 받을 때, 상근이의 시작위치, 불 위치는 각각의 큐에 저장하고, 탈출 지점 좌표를 벡터에 저장한다. 이후, 각각의 큐를 바탕으로 BFS를 진행하고, 각각의 map 정보를 저장한다. 탈출 지점 좌표를 탐색하여, 불 위치를 BFS한 맵, 상근이 위치를 BFS한 맵의 값을 비교하고 상근이 위치를 BFS한 맵의 탈출 지점 값이 더 작다면 최솟값을 비교한다. #include using namespace std;int dx[4] = {0, 0, 1, -1};int dy[4] = {1, -1, 0, 0};int n, h, w;vecto..

문제M * N * H로 이루어진 박스에 토마토들이 담겨 있는데, 익은 토마토가 되기 위해서는 안 익은 토마토 근처에 익은 토마토가 있을 때, 하루가 지나면 익은 토마토가 된다. 박스에 모든 토마토가 익은 토마토가 될려면 며칠이 지나야하는지 출력하는 문제이다. 입력 조건은 -1(토마토가 없는 박스), 0(안익은 토마토), 1(익은 토마토)이다.풀이3차원 배열에 박스 정보를 입력받고, 익은 토마토 좌표를 큐에 저장한 뒤, BFS를 이용하여 날짜를 계산했다. 큐가 비었을 때 BFS가 끝나므로 출력할 땐, count - 1를 한다.#include using namespace std;int dx[6] = {0, 0, 1, -1,0,0 };int dz[6] = {1, -1, 0, 0,0,0};int dy[6] = ..