본문 바로가기

알고리즘/순열

 (7)
백준 1987번: 알파벳 dfs import java.util.Arrays; import java.util.HashMap; import java.util.LinkedList; import java.util.Map; import java.util.Queue; import java.util.Scanner; public class baekjoon1987 { static int h; static int w; static char[][] info; static HashMap visit = new HashMap(); static int[] aryY = { 0, 0, -1, 1 }; static int[] aryX = { -1, 1, 0, 0 }; static int res = 0; public static void main(String[]..
[JAVA] 백준 2580번: 스도쿠 문제 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루어진 정사각형 판 위에서 이뤄지는데, 게임 시작 전 일부 칸에는 1부터 9까지의 숫자 중 하나가 쓰여 있다. 나머지 빈 칸을 채우는 방식은 다음과 같다. 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다. 굵은 선으로 구분되어 있는 3x3 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타나야 한다. 위의 예의 경우, 첫째 줄에는 1을 제외한 나머지 2부터 9까지의 숫자들이 이미 나타나 있으므로 첫째 줄 빈칸에는 1이 들어가야 한다. 또한 위쪽 가운데 위치한 3x3 정사각형의 ..
[JAVA] 백준 9663번: N-Queen 백트래킹 문제 N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N이 주어진다. (1 ≤ N < 15) 출력 첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다. import java.util.Arrays; import java.util.Scanner; public class baekjoon9663 { static int[] info; static int n; static int res; public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextI..
[JAVA] 백준 14889번: 스타트와 링크 문제 오늘은 스타트링크에 다니는 사람들이 모여서 축구를 해보려고 한다. 축구는 평일 오후에 하고 의무 참석도 아니다. 축구를 하기 위해 모인 사람은 총 N명이고 신기하게도 N은 짝수이다. 이제 N/2명으로 이루어진 스타트 팀과 링크 팀으로 사람들을 나눠야 한다. BOJ를 운영하는 회사 답게 사람에게 번호를 1부터 N까지로 배정했고, 아래와 같은 능력치를 조사했다. 능력치 Sij는 i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치이다. 팀의 능력치는 팀에 속한 모든 쌍의 능력치 Sij의 합이다. Sij는 Sji와 다를 수도 있으며, i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치는 Sij와 Sji이다. N=4이고, S가 아래와 같은 경우를 살펴보자. 1 2 3 4 ..
[JAVA] 백준 14888번: 연산자 끼워넣기 문제 N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다. 우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다. 이때, 주어진 수의 순서를 바꾸면 안 된다. 예를 들어, 6개의 수로 이루어진 수열이 1, 2, 3, 4, 5, 6이고, 주어진 연산자가 덧셈(+) 2개, 뺄셈(-) 1개, 곱셈(×) 1개, 나눗셈(÷) 1개인 경우에는 총 60가지의 식을 만들 수 있다. 예를 들어, 아래와 같은 식을 만들 수 있다. 1+2+3-4x5%6 1%2+3+4-5x6 1+2%3x4-5+6 1%2x3-4+5+6 식의 계산은 연산자 우선..
[JAVA] 백준 1339번: 단어수학 문제풀이 알파벳으로 이루어진 여러 문자열이 주어지고, 이 문자열끼리 덧셈을 해야하는데 가장 큰 값을 도출하도록 알파벳에 숫자를 할당해야하는 문제이다. 예를 들어, ABAB + CCDD를 한다고 가정하면 C = 9, A=8, B=7, D=6 이 들어가야 할 것이다. 값의 범위는 0~9 이고, 큰 값부터 한개씩 가장 큰 자리수에 존재하는 알파벳에 한개 씩 할당해 주면 된다. 가장 큰 자리수에 존재하는 알파벳은 어떻게 알아낼 것인가? ABAB = (1000 * A) + (100 + B) + (10 * A )+ (1 * B) CCDD = (1000 * C) + (100 + C) + (10 * D)+ (1 * D) A = 1010 B = 101 C = 1100 D = 11 위와 같이 연산하면 C > A > B >..
[JAVA] 백준 2529번: 부등호 부등호를 만족하는 최소값과 최대값을 구하라 첫 자리가 0인 경우도 정수에 포함한다. import java.util.ArrayList; import java.util.Scanner; public class baekjoon2529_2 { static String[] infoAry = { "0", "1", "2", "3", "4", "5", "6", "7", "8", "9" }; // static String[] infoAry = { "0", "1", "2" }; static boolean[] visit = new boolean[10]; static String[] info; static int n; static ArrayList ary = new ArrayList(); public static void ma..

티스토리툴바