본문 바로가기

알고리즘 (2020 : 08 : 10 ~ )/완전탐색

 (25)
[백준 / BOJ] 9663 N-Queen 문제 출처 : www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net N*N의 체스판에 N개의 퀸을 서로 공격할수없도록 배치해야한다. 이때, 퀸을 놓는 경우의 수를 구하는 문제다. 풀이 N의 최댓값이 15이다. 따라서, 최악의경우 15 * 15의 판에 15개의 퀸을 놓는 경우이므로, 15! * 15^3 만큼 반복하게된다. 따라서, 모든경우를 봐줄려하면 시간초과가 나게된다. 시간초과를 피하기 위해서 체크배열을 이용해서 해당 위치에 퀸을 놓을수있는지 없는지 봐줘야한다. 퀸은 가로 세로..
[백준 / BOJ] 18512 점프 점프 문제 출처 : www.acmicpc.net/problem/18512 18512번: 점프 점프 첫째 줄에 두 사람이 한 번에 멀리뛰기를 하는 거리 X, Y와 시작 지점의 위치 값 P1, P2가 각각 공백을 기준으로 구분되어 자연수로 주어진다. (1 ≤ X, Y, P1, P2 ≤ 100) www.acmicpc.net 두 학생 A,B가 각각의 시작위치에서 출발하고 P1 P2만큼 움직일때, 가장 처음 만나게 되는 지점을 출력하는 문제다. 풀이 P1 P2에서 시작했을때 두 학생의 시작지점과 한번에 점프하는 거리가 학생끼리 서로소인지?? 판별해서 푸는문제 같았는데, X,Y,P1,P2의 최댓값이 100 이길래 완전탐색으로 풀어줬다. 계산해보지는 않았지만, 최댓값이 100밖에 안되므로, 10만번 돌았을때도 만나지 않는..
[백준 / BOJ] 3042 트리플렛 문제 출처 : www.acmicpc.net/problem/3042 3042번: 트리플렛 상근이와 창영이는 트리플렛이라는 게임을 하고 있다. 이 게임을 하려면 칠판에 N*N 그리드를 그려야 한다. 그 다음 알파벳 대문자를 적절히 각 칸에 써 넣는다. 한 알파벳을 여러 칸에 쓸 수는 �� www.acmicpc.net N*N그리드가 주어지고, 각 칸에 알파벳 혹은 '.'이 주어진다. 이때 3개의 알파벳이 한 직선을 이루면 이를 트리플렛 이라고 한다. 예를들어, ...A ..B. .C.. D... 은 ABC가 하나의 트리플렛을 이룬다, BCD가 트리플렛을 이룬다... 라고 생각하면된다. 풀이 그냥 완전탐색을 할경우, N이 최대 100이고 N*N이므로, 칸의 총 갯수는 100*100 = 10000개이다. 여기서 ..
[백준 / BOJ] 1034 램프 문제 출처 : www.acmicpc.net/problem/1034 1034번: 램프 첫째 줄에 N과 M이 주어진다. N은 행의 개수이고, M은 열의 개수이다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 램프의 상태가 주어진다. 1이 켜져있는 상태이고, 0이 꺼져� www.acmicpc.net N*M배열의 각 칸마다 램프가 들어있고, 한 행이 전부 켜져있을때, 그 행이 켜져있다고 말한다. 램프는 껏다킬수있는데, 한 램프를 선택해서 램프를 키면, 그 램프가 들어있는 행의 모든 열이 다 켜진다. N*M배열의 크기와 각 칸에 들어있는 램프의 상태가 주어졌을때, K번 램프를 껏다킨후 켜져있는 행의 최댓값을 구하는 문제다. 풀이 완전탐색으로 접근하면 시간초과가 날거같아서 ((1000 *..
[백준 / BOJ] 17349 1루수가 누구야 문제 출처 : www.acmicpc.net/problem/17349 17349번: 1루수가 누구야 (1 2)가 거짓말이라면, 선수 2가 1루수라는 주장과 1루수가 아니라는 주장이 동시에 존재하여 모순이다. (0 4)가 거짓말인 경우도, 마찬가지의 이유로 모순이다. (0 2)가 거짓말인 경우, 선수 2를 유�� www.acmicpc.net 총 9명의 선수중 1루수가 누구인지 찾는 문제이다. 9개의 줄에거쳐 각 선수가 주장을하는데 무조건 한명은 거짓말을 하고있다. 선수들의 주장은 1 A: 선수 A가 1루수이다. 0 A: 선수 A는 1루수가 아니다. 로 나타난다. (단, 1루수를 찾을수 없으면 -1을 출력한다.) 풀이 "한명의 선수가 거짓말을 하고있다." 는 조건이 있으니, 1번 선수가 거짓말을 할때, 2번 ..
[백준 / BOJ] 1079번 마피아 문제 출처 : www.acmicpc.net/problem/1079 1079번: 마피아 첫째 줄에 참가자의 수 N이 주어진다. 둘째 줄에는 각 참가자의 유죄 지수가 주어진다. 셋째 줄부터 N개의 줄에는 배열 R이 주어진다. 마지막 줄에는 은진이의 참가자 번호가 주어진다. N은 16보다 www.acmicpc.net 은진이는 게임에서 마지막남은 마피아이다. 각 시민에게는 유죄지수가 있다. 1. 남아있는 시민의 수가 짝수일때는 밤이되서 시민을 한명 죽일수있다. 참가자 i가 죽었을때, 다른 참가자 j의 유죄지수는 R[i][j]만큼 변한다. 2. 낮에는 살아있는 참가자중 유죄지수가 가장 높은 참가자를 죽인다. 은진이는 되도록이면 이 게임을 오래 하고 싶다. 은진이가 이 게임에 정말 천재적으로 임하여 매번 최적의 선..
[백준 / BOJ] 2798 블랙잭 문제 출처 : www.acmicpc.net/problem/2798 2798번: 블랙잭 문제 카지노에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다. 카드의 합이 21을 넘지 않는 한도 내에서, 카드의 합을 최대한 크게 만드는 게임이다. 블랙잭은 카지노마다 다양한 규정이 �� www.acmicpc.net N과 M이 주어지고, N개의 카드가 주어진다. 이 때, 카드 3개를 골랐을때, M을 넘지않으면서, M에 가장 근접한 수를 찾는 문제다. 풀이 N의 최댓값이 100이다. 100개의 칸에서 중복없이 3개를 선택하는 경우이므로, 100C3 만큼 반복해서, 시간초과가 나지않는다. 카드들중 임의의 카드 3개를 선택했을때 M에가장 근접한지 확인하고, 근접한다면 출력값을 update 해주고 다음으로 선택할 카드3..
[백준 / BOJ] 14754 Pizza Boxes 문제 출처 : 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 해설 n과 m이 주어지고, 각 칸에 해당하는 값이 주어진다. 이때, n * m 육면체를 정면, 옆면에서 봤을때, 모양은 각 줄에..

티스토리툴바