문제 문제 바로가기> BOJ 1799번: 비숍 1799번: 비숍 첫째 줄에 체스판의 크기가 주어진다. 체스판의 크기는 10이하의 자연수이다. 둘째 줄부터 아래의 예와 같이 체스판의 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 체스판 한 줄 단위로 www.acmicpc.net 풀이 문제의 핵심은 "비숍의 이동 방식(체스판의 색깔)" 이다. 비숍은 대각선으로만 이동 가능하고, 이는 이동 전과 이동 후의 체스판의 색깔이 같음을 의미한다. 이 부분이 왜 핵심인가!! 그 이유는, 같은 색깔에 있는 비숍끼리만 영향을 끼칠 가능성이 있기 때문!! 이다. 따라서 전체 경우의 수인 2^(N*N)을 한번에 모두 탐색하는 것이 아닌, 검은색, 흰색으로 나누어 2번 탐색 + backtracking 하여, 2(검은색,..

문제 문제 바로가기> BOJ 17825번: 주사위 윷놀이 17825번: 주사위 윷놀이 주사위 윷놀이는 다음과 같은 게임판에서 하는 게임이다. 처음에는 시작 칸에 말 4개가 있다. 말은 게임판에 그려진 화살표의 방향대로만 이동할 수 있다. 말이 파란색 칸에서 이동을 시작하면 www.acmicpc.net 풀이 각 칸에서 이동해야하는 다음칸, 점수를 저장해 두어야 하는데, 이 때 약간의 노가다 작업?이 필요하다. 그 외에는 단순 백트래킹 문제이다 ! 💡 문제 해결 Point 처음에 파란지점 때문에 2차원 배열([이동칸][현위치] = 다음위치)을 만들어서 바로 이동하게 하려고 했는데, 이렇게 하는 경우, 너무 많은 노가다 작업이 필요했다,, 개인적으로, blueP 지점을 별도 배열로 가지고 있는 부분이 중요한 ..

문제 문제 바로가기> BOJ 10597번: 순열장난 10597번: 순열장난 kriii는 1부터 N까지의 수로 이루어진 순열을 파일로 저장해 놓았다. 모든 수는 10진수로 이루어져 있고, 모두 공백으로 분리되어 있다. 그런데 sujin이 그 파일의 모든 공백을 지워버렸다! kriii가 순 www.acmicpc.net 풀이 1 ≤ N ≤ 50이므로, 수를 한개 또는 두개 씩 잘라가며, 순열을 만들어 본다! 이 때, 이미 사용한 수, 수열의 범위를 넘어서는 수의 경우는 더 이상 탐색해 볼 필요가 없다. C++ #include #include #define MAX 51 using namespace std; int N, len; vector v; bool isuse[MAX]; void solution(string..

문제 문제 바로가기> BOJ 9663번: N-Queen 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 `board[row] = col` 값을 저장하여, 2차원 배열이 아닌 1차원 배열로 문제를 해결할 수 있다. 퀸을 놓을 때 가로, 세로, 대각선을 확인해야 하는데, solution() 함수에서 한 줄에 하나를 놓고, 유망한 경우, 다음 solution을 호출하기 때문에 자동으로 한 row에는 퀸이 하나만 놓인다. 따라서 대각선과 동일한 column에 퀸이 놓여 있는지를 통해 해당 위치가 유망한지 판단해주면 된다. C+..

문제 문제 바로가기> BOJ 2023번: 신기한 소수 2023번: 신기한 소수 수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수 www.acmicpc.net 풀이 왼쪽 부터 자리 수를 늘려가면서 소수인지 판정한다. cnt == N , 즉 N 자리가 되기전에, 소수가 아니라고 판별되면, 그 이후로는 더 볼 필요가 없다! 첫 째 자리 수가 소수일 수 있는 경우는 `2, 3, 5, 7` 뿐이고, 둘 째 자리부터 짝수로 끝나는 경우는, 소수가 될 수 없다. 소수를 판별할 때는 N의 제곱근 까지만으로 나누어 보면 된다! 💡 소수 판별 시 N의 제곱근 까지만 나누..

문제 문제 바로가기> BOJ 15684번: 사다리 조작 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 풀이 ** 시간 초과 방지를 위한 Tip ** 1. h번 가로선에서 사다리를 조작한 경우, 그 다음 조작할 사다리는 h번 가로선 부터 찾아가면 된다. → 이미 앞에서 계산했으므로 ! (이 부분이 중요 ) 2. 가로선을 연속해서 나란히 놓을 필요가 없기 때문에, `isLine[a][b] || isLine[a][b+1] || isLine[a][b-1]` 다음 중 하나라도 해당 된다면, 가로선을 놓을 필요가 없다..