본문 바로가기

Algorithm

 (2139)
(C++) - 백준(BOJ) 19939번 : 박 터뜨리기 https://www.acmicpc.net/problem/19939 19939번: 박 터뜨리기 $N$개의 공을 $K$개의 바구니에 문제의 규칙을 만족하면서 나눠 담을 수 있다면, 가장 많이 담긴 바구니와 가장 적게 담긴 바구니의 공의 개수 차이를 출력한다. 나눠 담을 수 없는 경우에는 -1을 www.acmicpc.net 공식을 찾아 푸는 수학문제였습니다. 📕 풀이방법 📔 입력 및 초기화 n, k 선언 후 입력받습니다. 📔 풀이과정 겹치지 않으면서 최소 1개를 바구니에 배분해야하므로 1, 2, 3, .... , x 가 k개의 바구니에 담겨있는 모양이 됩니다. \sum_{1}^{x} p = n 이라는 공식이 성립합니다. \sum_{1}^{x} p = k(k+1)/2 = n 이 배분할 수 있는 최저 조건입니다..
(C++) - 백준(BOJ) 17265번 : 나의 인생에는 수학과 함께 https://www.acmicpc.net/problem/17265 17265번: 나의 인생에는 수학과 함께 세현이의 인생의 목표는 1분 1초 모든 순간 수학과 함께 살아가는 것이다. 그렇기 때문에 매일 수학을 생각하면서 살아가고 있다. 세현이는 밥을 먹을 때도 쌀알의 수를 계산하여 칼로리를 바로 www.acmicpc.net 완전탐색(brute force) 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 1. 바둑판 정보를 입력할 char형 이차원 배열 board, maxD, minD, n을 선언합니다. 2. n을 입력 후 바둑판의 정보를 board에 입력합니다. 📔 풀이과정 dfs를 수행하면서 밟은 바둑판의 칸 정보를 string s에 저장하다가 (n - 1행, n - 1열)에 도착했을 때 s를 통해 정..
(C++) - 백준(BOJ) 17521번 : Byte Coin https://www.acmicpc.net/problem/17521 17521번: Byte Coin 입력은 표준입력을 사용한다. 첫 번째 줄에 요일 수를 나타내는 양의 정수 n과 초기 현금 W(1 ≤ n ≤ 15, 1 ≤ W ≤ 100,000)가 주어진다. 다음 n 개의 줄에서, i번째 줄은 i일의 바이트 코인 가격을 나 www.acmicpc.net greedy문제였습니다. 📕 풀이방법 📔 입력 및 초기화 n, w, coinNum, 일차원 배열 coinPrice를 long long형으로 선언합니다. 📔 풀이과정 coinPrice[i] < coinPrice[i + 1] 이라면 i번째 날에서 매수, i+1번째 날에 매도하는 것이 무조건 이익을 취할 수 있는 방법입니다. i번째 산 코인의 개수를 coinNum..
(C++) - 백준(BOJ) 1253번 : 좋다 https://www.acmicpc.net/problem/1253 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 이분탐색으로 푼 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 1. n, ans, 일차원 배열 num을 선언 후 n만큼 수를 입력받습니다. 2. num을 오름차순으로 정렬해줍니다. 📔 풀이과정 오름차순으로 정렬되어 있으니 i번째 수를 두 수의 합으로 나타내려면 그 두 수의 위치는 무조건 0 ~ i-1 사이에 존재합니다. num[i+1]부터는 하나의 수 만으로도 num[i]를 넘기 때문에 두 개의 수에 대한 합으로 표현할 수 ..
(C++) - 백준(BOJ) 12833번 : XORXORXOR https://www.acmicpc.net/problem/12833 12833번: XORXORXOR 세 수 A, B, C를 입력 받은 다음, ( ( ( ( A XOR B ) XOR B ) XOR B ) … ) XOR B 형태로 연산을 C회 했을 때의 결과값을 출력하는 프로그램을 작성하시오. www.acmicpc.net XOR의 성질을 알 수 있는 수학문제였습니다. 📕 풀이방법 📔 입력 및 초기화 a, b, c, ans를 선언합니다. 그 후 a, b, c를 입력합니다. 📔 풀이과정 XOR는 같은 값의 비트에 대해 0을, 다른 값의 비트에 대해 1인 계산결과를 보여줍니다. 따라서 (a XOR b) XOR b를 하게 된다면 자기 자신이 나오는 특징을 가지게 됩니다. c가 짝수라면 XOR를 짝수번 실행하므로 a..
(C++) - 백준(BOJ) 1595번 : 북쪽나라의 도로 https://www.acmicpc.net/problem/1595 1595번: 북쪽나라의 도로 입력은 여러줄에 걸쳐 주어진다. 입력의 각 줄은 세 개의 양의 정수로 구성되어있는데, 각각은 차례대로 서로 다른 두 도시의 번호와 두 도시를 연결하는 도로의 길이를 의미한다. 모든 도로는 www.acmicpc.net dfs로 푼 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 인접 도시로 가는 경로가 1개인 연결그래프는 트리입니다. 이 트리구조를 저장하기 위해 struct Edge를 만들어 양방향그래프를 저장합니다. 📔 풀이과정 단순히 건너간 간선이 최대라고 거리까지 최대가 되지는 않습니다. 또한 어떤 도시에서 다른 도시로 갈때는 말단 노드(도시)를 경유지로 가면 안됩니다. 출발도시에서 말단 노드(도시)로 가는 ..
(C++) - 백준(BOJ) 17485~6번 : 진우의 달 여행 (Small, Large) https://www.acmicpc.net/problem/17484 17484번: 진우의 달 여행 (Small) 첫줄에 지구와 달 사이 공간을 나타내는 행렬의 크기를 나타내는 N, M (2≤ N, M ≤ 6)이 주어진다. 다음 N줄 동안 각 행렬의 원소 값이 주어진다. 각 행렬의 원소값은 100 이하의 자연수이다. www.acmicpc.net https://www.acmicpc.net/problem/17485 17485번: 진우의 달 여행 (Large) 첫줄에 지구와 달 사이 공간을 나타내는 행렬의 크기를 나타내는 N, M (2 ≤ N, M ≤ 1000)이 주어진다. 다음 N줄 동안 각 행렬의 원소 값이 주어진다. 각 행렬의 원소값은 100 이하의 자연수이다. www.acmicpc.net dp 문제였습니..
(C++) - 백준(BOJ) 1823번 : 수확, 13002번 : Happy Cow https://www.acmicpc.net/problem/1823 1823번: 수확 첫째 줄에 벼의 개수 N(1 ≤ N ≤ 2,000)이 주어지고 두 번째 줄부터 N+1번쨰 줄까지 벼의 가치 v(i) (1 ≤ v(i) ≤ 1,000) 가 주어진다. www.acmicpc.net https://www.acmicpc.net/problem/13002 13002번: Happy Cow 천나라에 살고있는 민호는 애지중지하는 소 한마리가 있다. 소의 행복은 곧 민호의 행복이기 때문에 가지고 있는 전재산을 털어 최고로 맛있는 여물 N개를 구매 했다. 민호는 여물을 관리하기 www.acmicpc.net dp 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 1. n, 벼의 가치를 입력받을 일차원 배열 a, 점화식을 계산할 이..

티스토리툴바