🔗 문제 1339번: 단어 수학 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 🖍 풀이 1) 수학적 접근 못 풀어서 이 분의 풀이를 참고했습니다. 설명도 정말 잘 되어 있으니 참고 바랍니다. 최고임. 🔗 https://mygumi.tistory.com/156 예를 들어 2개의 문자 ABC + BCD를 더한다고 생각해보자. ABC = 100A + 10B + C BCD = 100B + 10C + D ABC + BCD = 100A + 110B + 11C + D 이것을 내림차순으로 정렬한다면 어떻게 해야할지 ..

🔗 문제 9663번: N-Queen 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 🖍 풀이 먼저 백트래킹을 이용한 기초적인 문제로 백트래킹이 뭔지 알고 풀면 더 좋을 것 같다. 백트래킹이란? Promising을 통해 과정을 Prunning하는 기법 DFS(깊이 우선 탐색)과 비슷하지만 조건을 잘 활용하여 유망하지 않은 경로는 가지치기를 통해 진행하지 않는다. 이를 통해 메모리와 시간을 아낄 수 있다. N-Queen의 조건 퀸이 놓여진 수직, 수평에 다른 퀸을 놓을 수 없다. 퀸이 놓여진 대각선에 다른 퀸을 놓을 수 없다. ..

🔗 문제 2580번: 스도쿠 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 🖍 풀이 스도쿠 칸에 값을 넣는 조건 가로와 세로에 중복된 숫자가 올 수 없다. 3*3짜리 9칸으로 나눴을 때 영역에 중복된 숫자가 올 수 없다. 이 조건을 잘 생각해서 완전 탐색을 해보자. 입력 빈칸 탐색하기 싫어서 입력을 받을 때 빈칸인 좌표를 zeros에 저장해주었다. 완전 탐색 for(int i=1; i

🔗 문제 2339번: 석판 자르기 2339번: 석판 자르기 하나 이상의 불순물과 보석 결정체로 이루어진 석판을 여러 조각으로 나누어 가공해서, 보다 높은 가치를 얻을 수 있도록 만들려고 한다. 이때, 높은 가치의 석판을 만들기 위해서는 석판을 여 www.acmicpc.net 🖍 풀이 문제를 풀기 위해서는 총 3가지 과정을 정확히 이해해야 합니다. 석판을 자를 수 있는 조건 석판 자르기 재귀적으로 석판 자르기 (내가 막혔던 부분) 석판을 자를 수 있는 조건 이전과 다른 방향으로 잘라야 한다. (가로, 세로의 반복) 자르고자 하는 열이나 행은 불순물을 포함한다. 자르고자 하는 열이나 행에 보석이 있으면 자를 수 없다. 잘랐을 때 반드시 석판이 2개로 나뉘어야 한다. 불순물을 모두 제거한 후 조각난 각각의 보..

🔗 문제 14501번: 퇴사 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 🖍 풀이 일을 했을 경우와 일을 하지 않았을 경우로 상황을 나눠 생각할 수 있다. i 날에 일을 한 경우: i + T[i] 에 수익이 전에 벌어 놓은 돈 + P[i] 이 된다. i 날에 일을 하지 않을 경우: i+T[i]날 수익에 변동이 없다. 이걸 재귀함수로 짠다면? 간단하게 생각하면 완전 탐색할 수 있다. void solve(int days, int profit) { if(days == N+1) { return; } solve(days + T[days], profit + P[days]); solve(days + 1, profit) } 하지만 재귀함수는 호출된 함수 메모..

🔗 문제 1405번: 미친 로봇 1405번: 미친 로봇 첫째 줄에 N, 동쪽으로 이동할 확률, 서쪽으로 이동할 확률, 남쪽으로 이동할 확률, 북쪽으로 이동할 확률이 주어진다. N은 14보다 작거나 같은 자연수이고, 모든 확률은 100보다 작거나 같은 자 www.acmicpc.net 🖍 풀이 이 문제 전에 '부분수열의 합'을 먼저 풀며 백트래킹에 대해 알고 푸는 걸 권장드립니다. 조건을 정리해보자. 로봇은 동서남북 중 하나를 한칸씩 N번 이동한다. N은 14보다 작거나 같은 자연수다. 동서남북으로 이동할 확률이 있다. → 확률이 0만 아니면 이동이 가능하다. 재방문하지 않으면서 이동하는게 단순한 이동이다. 그냥 재방문하지 않고 N번 이동하는 확률만 구하면 된다. 상하좌우 한 방향으로만 14번 가도 재방문 ..

🔗 문제 1759번: 암호 만들기 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 암호는 서로 다른 L개의 알파벳 소문자들로 구성되며 최소 한 개의 모음(a, e, i, o, u)과 최소 두 개의 자음으로 구성되어 있다고 알려져 있다. 또한 정렬된 문자열을 선호하는 조교들의 성향으로 미루어 보아 암호를 이루는 알파벳이 암호에서 증가하는 순서로 배열되었을 것이라고 추측된다. 즉, abc는 가능성이 있는 암호이지만 bac는 그렇지 않다. 새 보안 시스템에서 조교들이 암호로 사용했을 법한 문자의 종류는 C가지가 있다고 ..

🔗 문제 1189번: 컴백홈 1189번: 컴백홈 첫 줄에 정수 R(1 ≤ R ≤ 5), C(1 ≤ C ≤ 5), K(1 ≤ K ≤ R×C)가 공백으로 구분되어 주어진다. 두 번째부터 R+1번째 줄까지는 R×C 맵의 정보를 나타내는 '.'과 'T'로 구성된 길이가 C인 문자열이 주어진다 www.acmicpc.net 🖍 풀이 한수는 캠프를 마치고 집에 돌아가려 한다. 한수는 현재 왼쪽 아래점에 있고 집은 오른쪽 위에 있다. 그리고 한수는 집에 돌아가는 방법이 다양하다. 단, 한수는 똑똑하여 한번 지나친 곳을 다시 방문하지는 않는다. 위 예제는 한수가 집에 돌아갈 수 있는 모든 경우를 나타낸 것이다. T로 표시된 부분은 가지 못하는 부분이다. 문제는 R x C 맵에 못가는 부분이 주어지고 거리 K가 주어지면 ..

🔗 문제 2447번 - 별 찍기 - 10 2447번: 별 찍기 - 10 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 www.acmicpc.net 🖍 풀이 조각내서 출력하면 쉬운데 출력은 한 줄 단위라 애를 엄청 썼다. 그러다가 한 셀마다 공백' '인지, '*'을 찍을지 봐주게 되었다. 0, 0 0, 1 0, 2 1, 0 1, 1 1, 2 2, 0 2, 1 2, 2 패턴은 (1) 전체가 공백인 부분과 (2) N/3 패턴 부분으로 나뉜다. (1) 공백으로만 채워지는 공간은 전체 패턴을 9조각 냈을 때 (1, 1) 에 해당한다. (2) N/3..

🔗 문제 14889번: 스타트와 링크 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 🖍 풀이 어떻게 모든 경우의 수를 돌도록 함수를 짤지 고민만 하면 풀 수 있다. 이 문제에서는 팀원을 반으로 갈라야 한다. N이 6명이면 3명의 모일 수 있는 모든 조합을 구해야한다. 그렇다면 팀원을 N/2명 모일 때까지 재귀함수를 호출하도록 작성해준다. N/2명이 모이면 능력치 차이를 구하고 다시 되돌아가 조합하지 않았던 팀원에 접근한다. 팀원을 한명씩 모은다. 팀원이 다 모였다. 능력치 계산을 하고 2번으로 간다. 팀원이 다 모일 때까지 반복 ..