[백준 / 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 난이도: solved.ac 골드 3 알고리즘 분류 그래프 이론, 데이크스트라 (Dijkstra) 접근 방법 (풀이 1) 먼저 각 노드 i에서 X로의 최단 거리를 파악하기 위해 모든 노드에 대해 다익스트라 알고리즘을 N번 사용한다. 그리고 dist[X]의 결과를 ans[i]에 저장한다. 그 다음 X에서 다른 모든 노드로의 최단 거리를 파악하는 X를 기준으로 한 다익스트..

• format_list_bulleted PS/백준
• · 2023. 8. 15.
• textsms

[백준 / C++] 1629번: 곱셈 (그리디 풀이...?)

https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 난이도: solved.ac 실버 1 분할 정복(Divide and Conquer)을 이용해 푸신 분들이 많던데 나는 그리디(?)로 풀어보았다. A를 B번 곱하는 것은 A의 B승을 구하라는 것과 같다. 따라서 A를 A^B로 만들어주기로 했다. A는 A^1이다. A^1을 A^B로 만드는 과정은 1을 B로 만드는 과정과 같다. 우선 거듭제곱의 성질 중 a^b * a^b = a^(2b) 를 알아야 한다. 2^3 * 2^3 = 2^6 (8 * 8 = 64)을 떠올리면 이..

• format_list_bulleted PS/백준
• · 2023. 8. 14.
• textsms

[백준 / C++] 11660번: 구간 합 구하기 5

https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 난이도: solved.ac 실버 1 알고리즘 분류 다이나믹 프로그래밍 (dp), 누적 합 (prefix sum) 접근 방법 각 행 별로 1열부터의 누적 합으로 배열에 저장한다. Ex. sum[3][5] = (3,1)부터 (3,5)까지의 합 sum[4][7] = (4,1)부터 (4,7)까지의 합 그리고 x1, y1, x2, y2를 입력받아 (x1, y1)부..

• format_list_bulleted PS/백준
• · 2023. 8. 8.
• textsms

[백준 / C++] 9019번: DSLR

https://www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 난이도: solved.ac 골드 4 알고리즘 분류 그래프 탐색 (BFS) 접근 방법 BFS 함수에서 현재 숫자에서 D, S, L, R 연산을 해 큐에 집어 넣는다. 그리고 visited 배열을 통해 방문한 숫자 (0 ~ 9999)를 체크하여 중복된 숫자를 방문하지 않도록 해준다. 구현 방법 현재 레지스터의 숫자를 저장할 int 형과 현재까지의 연산과정을 적은 string 형을 pair..

• format_list_bulleted PS/백준
• · 2023. 8. 7.
• textsms

[백준 / C++] 2467번: 용액 (이분탐색 X, 투포인터 X, 조금 다른 풀이)

https://www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 난이도: solved.ac 골드 5 접근 방법 서로 다른 두 수의 합이 0과 가장 가까운 것을 찾아야 하는 문제다. 합이 0과 가장 가까우려면 어떤 특징이 있을지에 대해 생각해 보았다. 합이 0과 가까우면, 두 수의 절댓값이 서로 비슷하다는 특징이 있다는 것을 발견했다. 이의 역은 성립하지 않는데, 절대값이 비슷하다고 합이 0과 가까운 것은 아니다. 하지만 합이 0과 가까운 두 수는 절대값이..

• format_list_bulleted PS/백준
• · 2023. 8. 7.
• textsms

[백준 / C++] 1662번: 압축

https://www.acmicpc.net/problem/1662 1662번: 압축 압축되지 않은 문자열 S가 주어졌을 때, 이 문자열중 어떤 부분 문자열은 K(Q)와 같이 압축 할 수 있다. K는 한자리 정수이고, Q는 0자리 이상의 문자열이다. 이 Q라는 문자열이 K번 반복된다는 뜻이 www.acmicpc.net 난이도: solved.ac 골드 5 손으로 이 문제를 푼다고 하면, 길이를 계산할 때 가장 안쪽 괄호부터 개수를 세어서 계산한다. 따라서 i 겹의 괄호 안에 몇 개의 숫자가 있는지를 저장하는 len이라는 배열을 만들었다. 편의상 괄호의 겹 수를 level이라고 표현하겠다. 예를 들어 level 3(세 겹의 괄호 안에 있는)인 숫자의 개수가 4개면, len[3] = 4가 된다. 여기서 주의해야..

• format_list_bulleted PS/백준
• · 2023. 8. 7.
• textsms