https://www.acmicpc.net/problem/1986 1986번: 체스 첫째 줄에는 체스 판의 크기 n과 m이 주어진다. (1 ≤ n, m ≤ 1000) 그리고 둘째 줄에는 Queen의 개수와 그 개수만큼의 Queen의 위치가 입력된다. 그리고 마찬가지로 셋째 줄에는 Knight의 개수와 위치, www.acmicpc.net 풀이 그냥 구현하면 되는데, 범위에 유의하면서 구현해야 한다. 코드 import java.util.*; import java.io.*; public class boj_1986_체스 { static int n, m, ans = 0; static int[][] Q, K, P; static char[][] chess; static boolean isRanged(int r, in..
https://www.acmicpc.net/problem/23889 23889번: 돌 굴러가유 $M$번째 줄에 걸쳐 가장 많은 모래성을 지키기 위해 벽을 설치해야 할 마을의 위치를 오름차순으로 출력한다. 가장 많은 모래성을 지킬 수 있는 경우가 두 가지 이상 존재할 경우, 사전순으로 가 www.acmicpc.net 풀이 매우 어렵게 푼 문제. 접근 방식도 생각해내기 어려웠는데 그걸 구현하는 것도 쉽지 않았다. 파이썬으로 하면 금방 끝나던데 자바로 하니까 쉽지가 않구만,, 돌이 굴러가기 시작하는 시작 위치에 벽을 둬야 하는건 당연하고, 그 중에서도 어디에 둬야 하는가를 고르는게 중요했다. 문제의 예시를 예로 들면 돌이 [1, 4, 5]번에 떨어지고 1~3 / 4 / 5~7까지로 나누어서 파괴되는 모래성을..
https://www.acmicpc.net/problem/1469 1469번: 숌 사이 수열 첫째 줄에 X의 크기 N이 주어진다. 둘째 줄에 X에 들어가는 수가 빈칸을 사이에 두고 주어진다. X의 크기는 8보다 작거나 같은 자연수이다. X의 원소는 0보다 크거나 같고 16보다 작거나 같은 정수 www.acmicpc.net 풀이 풀다가 틀려서 다른 코드를 참고했다.. 기존에 접근했던 방법은 만들 수 있는 모든 수열을 만들어 체크하는 것이었는데, 최대 길이가 20인 수열을 순열로 만드는건 20! 이기 때문에 시간초과가 나버렸다. 참고한 방법은 2*N 길이를 완성해가는 과정에서 조건을 만족하지 못하는 경우를 제거해나가는 방법이었다. 입력 수열 X를 오름차순으로 정렬하고, 현재 위치에서 숫자 i를 사용하지 않았..
https://school.programmers.co.kr/learn/courses/30/lessons/42842 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 분류는 완전탐색인데 푸는건 약수를 이용해서 풀었다. 완탐으로도 풀 수 있을 것 같은데 내가 푼 방식이 더 효율성이 높을 것 같다. 결국 카펫을 이루는 것은 노란색으로 이루어진 판을 갈색으로 한 칸씩 감싸는 것이기 때문에, 노란색이 어떻게 이루어져 있는지 결정하고 가로/세로로 +2씩만 하면 카펫이 구성되는 것을 이용한다. 코드 class Solution { public int[] solutio..
https://www.acmicpc.net/problem/2404 2404번: 단위 분수로 분할 첫째 줄에 양의 정수 p, q, a, n이 입력된다. (1 ≤ p, q ≤ 800, 1 ≤ a ≤ 12000, 1 ≤ n ≤ 7) www.acmicpc.net 풀이 좀 많이 어려웠다. 시간 제한이나 범위로 봐서는 완탐으로 돌리는게 맞는데 어딜 어떻게 잡고 돌려야 할지 감이 오지 않았다. 이것만 떠올리면 문제에 접근하는데 감이 확 온다. a/b=c/d ac=bd 즉 a/b를 주어진 p/q라고 생각하고, c/d를 만들어진 단위 분수라고 생각했을 때 p*d==q*c를 만족하는 경우를 세면 되는 것이다. 코드 package backtracking; import java.util.*; import java.io.*; ..
https://www.acmicpc.net/problem/25421 25421번: 조건에 맞는 정수의 개수 2개의 자릿수를 갖고 첫 번째 자리의 숫자와 두 번째 자리의 숫자의 차이가 2보다 작거나 같은 양의 정수 11, 12, 13, 21, 22, 23, 24, 31, 32, ... , 97, 98, 99가 A에 해당된다. 따라서 정답은 39이다. www.acmicpc.net 문제 분석 & 풀이 간단한 DP문제다. 많이 가볼 필요 없이 n=3까지만 손으로 세보면 규칙을 쉽게 파악할 수 있다. 점화식은 dp[n][i] = dp[n-1][i-2] + dp[n-1][i-1] + dp[n-1][i] + dp[n-1][i+1] + dp[n-1][i+2]. 1, 2, 8, 9일 때 예외처리만 신경쓰면 된다. 코드 ..
https://school.programmers.co.kr/learn/courses/30/lessons/131127?language=java 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제를 읽고 든 생각은 그냥 문제가 제시한대로 따라가면 풀면 될 것 같은데? 라는 생각이 들었다. 첫 번째 풀이 단순하게 discount 배열의 0번째부터 discount.length - 10까지 반복문을 돌면서 10개씩 자르며 원하는 수량을 다 채웠는지 체크한다. import java.util.*; class Solution { private boolean canReg..
https://www.acmicpc.net/problem/1744 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 문제 분석 수열 N이 주어졌을 때, 수열의 두 수를 묶어서 (순서는 상관없음) 묶은 수들의 합이 최대가 되도록 하는 문제. 묶은 두 수는 곱해지며, 수는 한 번만 묶을 수 있고, 묶지 않을 수도 있다. 예전에 풀었던 문제인데 뭔가 greedy 하지 못하다는 생각이 들어 백준에서 더 깔끔하게 푸신 분들이 없나 참고하였다. 내 코드 import java.io.BufferedReader; import..
