본문 바로가기

algorithm

 (17)
백준 1078 - 뒤집음 https://www.acmicpc.net/problem/1078 1078번: 뒤집음 어떤 수를 뒤집는다는 것은 오른쪽부터 다시 쓰는것이다. 예를 들어, 1234를 뒤집으면 4321이 되고, 100을 뒤집으면 1이 된다. (앞에 0은 무시) 어떤 수 D가 주어질 때, x – (x를 뒤집은 수)가 D가 되는 www.acmicpc.net 정말 너무 어려운 문제였다. 애초에 이건 알고리즘 문제보다 수학 문제에 가까웠다. 정말 어렵지만, 설명할 수 있는 만큼 최대한 자세하게 설명했으니 도움이 되길 바란다. 공식분석하기 X에 대한 공식 $$ X = a_0 * 10^{L-1} + a_1 * 10^{L-2} +... + a_{L-1} * {10^0} $$ 이 때 자릿수는 0부터 센다. 먼저 X는 자릿수의 수 * 10..
백준 12094 - 2048(Hard) https://www.acmicpc.net/problem/12094 12094번: 2048 (Hard) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 보드 움직이기 먼저 보드를 움직이는 로직을 살펴보겠다. 간단하게 위로 움직이는 로직만 살펴본다. private static boolean move(Direction dir, int cnt) { int[][] map = maps[cnt]; boolean isChanged = false; switch (dir) { case TOP: for (int j = 0; j < N;..
백준 1007 - 벡터 매칭 https://www.acmicpc.net/problem/1007 1007번: 벡터 매칭 평면 상에 N개의 점이 찍혀있고, 그 점을 집합 P라고 하자. 집합 P의 벡터 매칭은 벡터의 집합인데, 모든 벡터는 집합 P의 한 점에서 시작해서, 또 다른 점에서 끝나는 벡터의 집합이다. 또, P에 속 www.acmicpc.net 문제해석 임의의 점이 N개 주어진다. 해당 N개의 점을 한 번씩 사용해서 만들 수 있는 벡터들의 합 중 최소값을 찾고, 길이를 구해야 한다. 점 (5, -3)에서 점 (2, 4)를 향하는 벡터는 다음과 같다. (2-5, 4+3) = (-3, 7) 또한 벡터 (-3, 7)과 벡터(2, -2)의 합은 다음과 같다. (-3 + 2, 7 -2) = (-1, 5) 또한 이렇게 만들어진 벡터의 길이..
백준 9202 - Boggle https://www.acmicpc.net/problem/9202 9202번: Boggle 각각의 Boggle에 대해, 얻을 수 있는 최대 점수, 가장 긴 단어, 찾은 단어의 개수를 출력한다. 한 Boggle에서 같은 단어를 여러 번 찾은 경우에는 한 번만 찾은 것으로 센다. 가장 긴 단어가 여러 개 www.acmicpc.net 접근방법 결론적으로 문제를 정리해보면 다음과 같다. 단어는 인접한 글자로 만들 수 있다. 한 블록(주사위)은 각 단어에 한 번까지만 사용가능하다. 단어를 만들면 그 단어의 길이에 따라 점수를 부여받는다. 주어진 Boggle grid에서 받을 수 있는 최대 점수와 찾을 수 있는 가장 긴 단어와 찾은 단어의 수를 구해라! 주의점 한 boggle에서 같은 단어 여러 번 찾기 불가능하다..
백준 12100 - 2048 (Easy) https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 문제 분석 문제 자체는 굉장히 간단하다. 처음에 주어진 블록에서 5번을 움직여서 가장 큰 블록을 찾으면 된다. 주의점은 한 번 움직일 때 같은 칸에서 두 번 합쳐질 수 없으며, 이동하는 방향을 우선으로 합쳐야 한다. 위 그림을 예시로 보자. 왼쪽 블록들을 위쪽으로 움직인 경우의 결과에 대한 그림이다. 결과블록의 첫번째 열을 보면 4가 중복되었지만 합쳐지지 못했다. 왜냐..
백준 15997 - 승부 예측 백준 승부예측 15997번: 승부 예측 첫 번째 줄에 조별리그를 진행할 국가명 네 개가 공백으로 구분되어 주어진다. 주어지는 모든 국가명은 알파벳 대문자로만 구성된 길이가 1 이상 10 이하인 문자열이다. 두 번째 줄부터 일곱 번 www.acmicpc.net 승부 예측 문제는 각 4팀이 다음 라운드로 진출할 확률이 얼마나 되는지 구하는 문제다. 처음에 봤을 때 막막했지만, 침착하게 생각하니 풀 수 있었다. 먼저 이 문제의 핵심은 다음과 같다. 위 그림처럼 모든 경우의 수에 대해 탐색을 해봐야 한다.(선은 다 그리진 못 했다.) 총 6경기를 하는데 각 6경기마다 이기고 비기고 지는 3가지 경우가 생기기때문에 모든 경우의 수는 3의 6승 = 729가 된다. 하지만 확률 중 0이 있으면 경우의 수는 줄어든다...
백준 14500 - 테트로미노 import java.io.*; import java.util.*; public class Main { static int data[][], row, column; static int xMove[] = {0, 0, 1, -1}, yMove[] = {1, -1, 0, 0}, max = 0; static boolean checked[][]; // 백준 14500 - 테트로미노 public static void main(String[] args) throws IOException { BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer rowColumn = new StringToke..
백준 1436 - 영화감독 숌 import java.io.*; public class Main { // 백준 1436 - 영화감독 숌 public static void main(String[] args) throws IOException { BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in)); int n = strToInt(bufferedReader.readLine()), seriesNum = 666, cnt = 0; while(true) { int num = seriesNum; while(num >= 666) { // 세 수가 연속적으로 6인 경우 cnt 증가 if(num % 10 == 6 && num / 10 % 10 == 6 &&..

티스토리툴바