본문 바로가기

알고리즘 문제풀이/백준134

[백준 1712] 손익분기점 www.acmicpc.net/problem/1712 1712번: 손익분기점 월드전자는 노트북을 제조하고 판매하는 회사이다. 노트북 판매 대수에 상관없이 매년 임대료, 재산세, 보험료, 급여 등 A만원의 고정 비용이 들며, 한 대의 노트북을 생산하는 데에는 재료비와 www.acmicpc.net #include #define ll long long using namespace std; ll a, b, c; int main(void) { scanf("%lld%lld%lld", &a, &b, &c); ll dif = c - b; if (0 >= dif) { printf("-1\n"); return 0; } ll res = a / dif; res++; printf("%lld\n", res); return 0; } 2021. 1. 6.
[백준 1504] 특정한 최단 경로 www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 다익스트라를 사용해서 노드 간의 거리를 구해준다. v1과 v2를 무조건 지나야 하므로 1 -> v1 -> v2 -> last 1 -> v2 -> v1 -> last 사이의 거리를 비교하여 작은 값을 리턴해준다. 양방향 그래프이고 비용이 같으므로 v1-> v2 == v2 -> v1이다. 따라서 사이 값을 mid로 한번만 구한다. 다익스트라 특성상 하나의 출발지로부터 모.. 2021. 1. 6.
[백준 2665] 미로만들기 www.acmicpc.net/problem/2665 2665번: 미로만들기 첫 줄에는 한 줄에 들어가는 방의 수 n(1≤n≤50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다. www.acmicpc.net 최소거리기 때문에 bfs나 다익스트라 둘다 사용가능하다. 다익스트라를 연습하기 위해! 다익스트라로 풀었다. 검은색은 비용을 1 하얀색은 비용을 0으로 하여 arr[n-1][n-1]까지 도달하는 최소 비용을 계산한다. 처음 모든 거리는 inf로 초기화한후 조건을 만족하면 거리를 업데이트한다. 최소 비용을 구해야 하기 때문에 pop한 cur가 목적지에 해당한다고 break하지 않고 끝까지 진행한다. #include #in.. 2021. 1. 6.
[백준 6588] 골드바흐의 추측 www.acmicpc.net/problem/6588 6588번: 골드바흐의 추측 각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 www.acmicpc.net 에라토스테네스의 체를 사용하여 1000000까지 소수를 체크하고 주어진 입력 t의 양끝점을 확인하여 start + end == t 가 되는 지점을 확인한다. #include using namespace std; int t; int arr[10000001]; int main(void) { for (int i = 2; i * i 2021. 1. 5.