본문 바로가기

알고리즘

 (82)
[백준] 14754번 Pizza Boxes C++ 문제풀이 https://www.acmicpc.net/problem/14754 14754번: Pizza Boxes Your program is to read from standard input. The input contains two integers, n and m (1 ≤ n, m ≤ 1,000), the number of rows and columns in the grid, respectively. Each of the following n lines contain m integers, the number of pizza boxes (heights) in www.acmicpc.net 문제 풀이 이 문제를 보자마자 그냥 먼저 생각난게 각 행, 열 별로 최대값을 찾아서 표시해주자! 라고 생각을 했다. 티어가 실버..
[백준] 14753번 MultiMax C++ 문제풀이 https://www.acmicpc.net/problem/14753 14753번: MultiMax There are n cards, each with an integer on it where two or more cards can have the same integer. From these cards, we want to select two or three cards such that the product of numbers on the selected cards is maximum. For example, assume that there are 6 www.acmicpc.net 문제 풀이 이 문제는 결국 숫자들 중에서 2개 or 3개의 카드를 뽑아 만들수 있는 숫자들 중 최대 숫자를 출력하는 문제였다. ..
[백준] 17626번 Four Squares C++ 문제풀이 https://www.acmicpc.net/problem/17626 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net 문제 풀이 그 전에 풀었던 문제가 그리디 문제여서 이번 문제도 별 생각 없이 그리디로 접근했다가 예제는 잘 나왔는데 틀렸다. 제곱수들의 배열을 만들고 n보다 작고, 가장 가까운 제곱수를 만나면 빼고 다시 n보다 작고, 가장 가까운 제곱수 찾아서~~ 이런식으로 구현했다. 이 경우 n = 21841이면 21841 = 104 ^ 2 + 105 ^ 2이 최적인데 나는 ..
[백준] 17521번 Byte Coin C++ 문제풀이 https://www.acmicpc.net/problem/17521 17521번: Byte Coin 입력은 표준입력을 사용한다. 첫 번째 줄에 요일 수를 나타내는 양의 정수 n과 초기 현금 W(1 ≤ n ≤ 15, 1 ≤ W ≤ 100,000)가 주어진다. 다음 n 개의 줄에서, i번째 줄은 i일의 바이트 코인 가격을 나 www.acmicpc.net 문제 풀이 그래프가 위로 올라가다 꺾이는 지점(고점)에서는 팔고, 그래프가 내려가다 올라가는 지점(저점)에서는 구매하는 식으로 코들를 작성했다. 다음날의 코인 가격을 알 수 있기 때문에 쉽게 구현할 수 있었다. 소스 코드 #include using namespace std; long long c_price[51] = { 0 }; int main() { lon..
[백준] 16283번 FARM C++ 문제풀이 https://www.acmicpc.net/problem/16283 16283번: Farm 입력은 표준입력을 사용한다. 첫 번째 줄에 네 정수 a, b, n, w가 한 줄에 주어진다. 1 ≤ a ≤ 1,000, 1 ≤ b ≤ 1,000, 2 ≤ n ≤ 1,000, 2 ≤ w ≤ 1,000,000이다. www.acmicpc.net 문제 풀이 이 문제 구현은 굉장히 간단했다. a * i + b *(n-i) == w 인지만 확인하면 되는건데, 문제에서 작은 디테일들에서 계속 실수를 했다. 1) 기르는 양과 염소는 각각 한 마리 이상이다 2) 만약 가능한 해가 2개 이상이거나 해가 없을 경우 -1을 출력한다 이 2개를 제대로 안 읽고 몇 번 틀렸다... ㅎ 다음부터는 문제를 잘 읽어야겠다! 소스 코드 #incl..
[백준] 20040번 사이클 게임 C++ 문제풀이 https://www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net 문제 풀이 맨 처음에 문제를 보자마자 이전에 풀었던 9466번 텀프로젝트 문제가 생각이 났다. 그래프 탐색 + 몇 번째에 사이클 완성되는지를 중점으로 코드를 작성했으나, 양방향 그래프이다 보니 사이클 찾는게 쉽지 않았고, 사이클을 찾는 코드를 작성했는데 시간복잡도가 매우 컸다. 다른 블로그 글들을 찾아보니, 그래프에 사이클이 있는지 여부를 판단하는 알고리즘에는 1) 무방향 그래프에서 사이클 ..
[백준] 20044번 Project Teams C++ 문제풀이 https://www.acmicpc.net/problem/20044 20044번: Project Teams 입력은 표준입력을 사용한다. 입력의 첫 번째 행에는 팀 수를 나타내는 양의 정수 n(1 ≤ n ≤ 5,000)이 주어진다. 그 다음 행에 학생 si 의 코딩 역량 w(si)를 나타내는 2n개의 양의 정수가 공백으로 www.acmicpc.net 문제 풀이 코딩 역량이 고르게 분포되기 위해서 정렬을 한 후 (코딩 역량이 가장 높은 학생, 코딩 역량이 가장 낮은 학생) , (코딩 역량이 2번째로 높은 학생, 코딩 역량이 2번째로 낮은 학생) ... 이런식으로 코드를 작성했다 소스 코드 #include #include #include using namespace std; vector player; int ..
[백준] 23246번 Sport Climbing Combined C++ 문제풀이 https://www.acmicpc.net/problem/23246 23246번: Sport Climbing Combined 입력은 표준입력을 사용한다. 첫째 줄에 선수의 명수를 나타내는 양의 정수 $n$ ($3 \le n \le 100$)이 주어진다. 이어 $n$개의 줄 각각에 네 정수 $b_i$, $p_i$, $q_i$, $r_i$가 주어지는데, $b_i$는 $i$번째 선수 www.acmicpc.net 문제 풀이 compare함수를 이용해 sort를 할 때 곱한 점수, 더한 점수를 고려해 sort를 해주었다. vector에는 id,(곱한점수, 더한점수)를 저장했다. 소스 코드 #include #include #include using namespace std; vector player; bool co..

티스토리툴바