💻 OnlineJudge/Baekjoon

[백준 / BOJ] C++ 1753 최단경로

https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 풀이 다익스트라 문제이다. 시작노드부터 최단 경로를 찾아내며, 최단경로에 저장되어있는 가중치를 출력한다. 우선 아래 이미지는 위의 입력을 그림으로 표현하였다. 우선순위큐를 이용하여 가중치 낮은순으로 저장을 하고, 해당 노드 방문시 시작지점으로부터 가중치를 더하여 비교를 하였을 때, 작은 경우만 출력을 해주면 된다. Code ( C++ ) #include #in..

[백준 / BOJ] C++ 1629 곱셈

https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 풀이 간단하지만 수의 크기때문에 생각의 시간이 필요했던 문제. (A * B) % C = (A%C * B%C) %C 위처럼 생각하여 C로 나누어 주어 숫자를 줄여 풀이가 가능하다. Code ( C++ ) #include using namespace std; long long pow(long long A, long long B, long long C) { if (B == 0) return 1; if (B == 1) return A % C; long long resu..

[백준 / BOJ] C++ 1504 특정한 최단 경로

https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 풀이 다익스트라 문제가 점점 익숙해지고 있다. 우선 문제를 살펴보자면, '특정 정점을 무조건 들려야한다' 라는 전제조건이 있다. 만약 정점을 2곳을 꼭 들려야 한다면 출발지점에서 해당 정점 2곳을 들리는 다익스트라 함수, 해당 정점으로부터 도착지점까지 가는 다익스트라 함수 즉 3번 탐색을 하면된다. 1. 시작점에서 입력받은 정점까지 가는 최단거리 2. ..

[백준 / BOJ] C++ 1238 파티

https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 풀이 다익스트라를 이용하는 문제이다. 1. 선언한 vector에 입력받은 시작위치에 끝점과 소요시간을 저장한다. 2. 시작 idx인 i 부터 X까지의 거리를 구한다. 3. X번 마을에서부터 다시 i 까지 돌아가는 거리를 구한다. 다익스트라 함수는 흔히 알고있는 다익스트라를 구현한다. 해당 거리를 저장하는 배열을 지속적으로 갱신해주고, 결과값에 저장후, 최대값을 찾아 ..

[백준 / BOJ] C++ 1167 트리의 지름

https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 풀이 트리 내에 임의의 두 점 사이중 가장 거리가 긴 점을 이어야한다. Root에서 가장 멀리 떨어진 정점으로 풀면 되겠지 했지만.. 안되서 해설을 찾아보았다. 루트에서 가장 멀리 떨어진 점과, 임의의 점에서 부터 가장 멀리 떨어진 정점의 합을 구하면 된다고한다. 저렇게만 보면 쉬운데.. 문제 풀이에 대해 아직 조금 미숙한것 같다. Code #include #include #inc..

[백준 / BOJ] C++ 1149 RGB거리

https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 풀이 연속적으로 같은색을 사용하지 않으면 되는 문제입니다. 2차원 배열에서 arr[i][0] 의 i 색이 연속적으로 동일하면 안되는 간단한 문제입니다. Code #include using namespace std; int N; int rgb[3]; int arr[999][3]; int result; int main() { ios::sync_with_stdio(false); c..

[백준 / BOJ] C++ 1043 거짓말

https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 풀이 과장된 이야기를 할 수 있는 파티의 갯수를 세어줘야한다. 우선 문제에서 주어지는 순으로 정리를 해보자. 첫번째 줄에는 N,M으로 사람의 수와 파티의 개수를 입력해준다. 두번째 줄에는 진실을 아는 사람의 수와 번호가 주어진다. 진실을 아는사람들을 체크하며, 해당 번호를 진실체크하는 queue에 넣어준다. 세번째 줄부터는 파티에 오는 사람의 명수와 번호가 주어진다. 입력받은 M만큼 반복하며, 해당 파티에 ..

[백준 / BOJ] C++ 6198 옥상 정원 꾸미기

https://www.acmicpc.net/problem/6198 6198번: 옥상 정원 꾸미기 문제 도시에는 N개의 빌딩이 있다. 빌딩 관리인들은 매우 성실 하기 때문에, 다른 빌딩의 옥상 정원을 벤치마킹 하고 싶어한다. i번째 빌딩의 키가 hi이고, 모든 빌딩은 일렬로 서 있고 오른쪽으 www.acmicpc.net 풀이 Stack을 이용한 간단한 문제이다. 스택에 i 번째 건물을 추가할때, 해당 건물보다 작거나 같은건 모두 pop을 해준다. 이후 pop해주고 stack에 남은 size만큼 total에 추가해주고, 다음 건물을 stack에 push 해준다. 그런데 해당 문제를 풀다가 total변수 자료형을 int로 하고, stack 자료형을 int로 하여 문제를 풀었으나, 계속 틀렸다고 하여서 다시 찾..