그리디

Algorithm/Baekjoon Online Judge
[Java] 백준 1744 (수 묶기) Gold 4
Problem : https://www.acmicpc.net/problem/1744 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net Approach Greedy한 문제이다. 아무 위치에 있는 두 수를 선택해도 되기 때문에, 먼저 정렬을 수행하는게 선택하기에 편하다. 문제 풀이에 앞서, 상식을 이용할 필요가 있다. 음수 두개를 곱하는 것이, 음수 두개를 더하는 것보다 값이 크다. 음수와 0은 곱하는 것이, 양수와 0은 더하는 것이 값이 크다. -1 두 개는 곱하는 것이, 1 두 개는 더하는 것이 값이 크다. ..
→2021.05.21
Algorithm/Baekjoon Online Judge
[Java] 백준 1285 (동전 뒤집기) Gold 1
Problem : https://www.acmicpc.net/problem/1285 1285번: 동전 뒤집기 첫째 줄에 20이하의 자연수 N이 주어진다. 둘째 줄부터 N줄에 걸쳐 N개씩 동전들의 초기 상태가 주어진다. 각 줄에는 한 행에 놓인 N개의 동전의 상태가 왼쪽부터 차례대로 주어지는데, 앞면이 위 www.acmicpc.net Approach Greedy + Bitmask 문제이다. 주요 로직은 다음과 같다. N x N 행렬이고, sum은 뒷면 동전의 총 개수이다. 행을 기준으로 뒤집을 행을 선택한다. (이 부분은 2^n 개수 만큼 존재한다.) 101 이라면 0, 2번째 행을 뒤집는다. 이제 선택한 행들을 뒤집을 건데, 열을 기준으로 먼저 뒤집는다. 101 이라면, 0,1,2 열 순서대로 0번째 행..
→2021.05.21
Algorithm/Baekjoon Online Judge
[Java] 백준 12100 (2048 Easy) Gold 2
Problem : https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net Approach BruteForce + 단순 구현 문제이다. break 문을 적절하게 넣어서 시간을 절약할 수 도 있겠지만, 그냥 4x4x4x4x4 = 1024 가짓수의 경우를 모두 검사하였다. 배열을 각각 왼쪽, 오른쪽, 위쪽, 아래쪽으로 미는 작업을 하는 메소드를 정의한 뒤, 4방향 중 중복허용하여 5가지 방향을 뽑아 적용하면 된다. 최대 크기 블..
→2021.04.05

• 이전
• 1
• 다음