14889번: 스타트와 링크

14889번: 스타트와 링크사용 언어: C++ 문제 요약총 N명의 사람이 있고, 이들을 두 팀(스타트 팀, 링크 팀)으로 나눈다. 각 팀에 속한 사람들의 능력치 합 차이를 최소화하는 것이 목표.능력치는 2차원 배열 S[i][j]로 주어지며,i번과 j번이 같은 팀일 때 더해지는 값은 S[i][j] + S[j][i].N은 항상 짝수이며, 두 팀은 N/2명씩 구성돼야 함.풀이1. 조합을 통해 팀을 나눈다N명 중 N/2명을 선택해서 스타트 팀을 구성하면,나머지 인원은 자동으로 링크 팀이 된다.→ 즉, 전체 경우의 수는 NC(N/2) 개의 조합.2. 각 조합에 대해 능력치 차이 계산스타트 팀의 능력치 = sum(S[i][j] + S[j][i]) (for i, j in 스타트 팀)링크 팀도 동일하게 계산두 팀의 차..

14888번: 연산자 끼워넣기

14888번: 연산자 끼워넣기사용 언어: C++ 문제 요약N개의 수와 N-1개의 연산자가 주어짐.수의 순서를 바꾸지 않고, 주어진 연산자를 모두 사용해 수식을 완성.연산 순서는 앞에서부터(왼쪽에서 오른쪽으로) 진행.가능한 모든 수식 결과 중 최댓값과 최솟값을 출력해야 함.풀이가능한 연산자 순열을 모두 탐색해야 하므로 백트래킹(DFS) 을 사용.각 재귀 단계마다 남아 있는 연산자 중 하나를 선택해 현재까지의 계산 결과를 갱신.나눗셈은 음수 처리를 주의해야 함 (C++ 기준: -(-a / b) 방식으로 처리).#include #include #include using namespace std;int N;vector A;int op[4]; // +, -, *, /int max_val = -1e9;int min..

2580번: 스도쿠

2580번: 스도쿠사용 언어: C++ 풀이문제 요약9×9 스도쿠 판에서, 일부 칸이 비어 있고(0으로 표시됨), 규칙에 맞게 모든 칸을 채워야 함.각 행에 1~9가 한번씩각 열에 1~9가 한번씩각 3×3 구역에 1~9가 한번씩풀이백트래킹 기법을 이용하여 모든 빈 칸에 대해 가능한 수를 대입하고,불가능한 경우 이전 상태로 돌아가서 다른 수를 시도.핵심 아이디어빈 칸을 순서대로 탐색하며 가능한 숫자를 시도숫자를 채울 때마다, 행/열/구역 사용 여부를 표시가능한 경우 다음 칸으로 재귀 호출실패하면 상태를 되돌리고 다음 숫자 시도 (백트래킹)구현 포인트각 행/열/3×3 구역에 대해 숫자 사용 여부를 확인하기 위해bool row[9][10], col[9][10], square[9][10] 배열을 사용한다.(i /..

1799번: 비숍 (BOJ C/C++)

16987번: 계란으로 계란치기 사용 언어: C++ 문제 서양 장기인 체스에는 대각선 방향으로 움직일 수 있는 비숍(bishop)이 있다. 과 같은 정사각형 체스판 위에 B라고 표시된 곳에 비숍이 있을 때 비숍은 대각선 방향으로 움직여 O로 표시된 칸에 있는 다른 말을 잡을 수 있다. 그런데 체스판 위에는 비숍이 놓일 수 없는 곳이 있다. 에서 체스판에 색칠된 부분은 비숍이 놓일 수 없다고 하자. 이와 같은 체스판에 서로가 서로를 잡을 수 없도록 하면서 비숍을 놓는다면 과 같이 최대 7개의 비숍을 놓을 수 있다. 색칠된 부분에는 비숍이 놓일 수 없지만 지나갈 수는 있다. 정사각형 체스판의 한 변에 놓인 칸의 개수를..

18809번: Gaaaaaaaaaarden

18809번: Gaaaaaaaaaarden 사용 언어: C++ 문제 길고 길었던 겨울이 끝나고 BOJ 마을에도 봄이 찾아왔다. BOJ 마을에서는 꽃을 마을 소유의 정원에 피우려고 한다. 정원은 땅과 호수로 이루어져 있고 2차원 격자판 모양이다. 인건비 절감을 위해 BOJ 마을에서는 직접 사람이 씨앗을 심는 대신 초록색 배양액과 빨간색 배양액을 땅에 적절하게 뿌려서 꽃을 피울 것이다. 이 때 배양액을 뿌릴 수 있는 땅은 미리 정해져있다. 배양액은 매 초마다 이전에 배양액이 도달한 적이 없는 인접한 땅으로 퍼져간다. 아래는 초록색 배양액 2개를 뿌렸을 때의 예시이다. 하얀색 칸은 배양액을 뿌릴 수 없는 땅을, 황토색 칸은 배양액을 뿌릴 수 있는 땅을, 하늘색 칸은 호수를 의미한다. 초록색 배양액과 빨간색 배..

16987번: 계란으로 계란치기 (BOJ C/C++)

16987번: 계란으로 계란치기 사용 언어: C++ 문제 원래 프로그래머의 기본 소양은 팔굽혀펴기를 단 한 개도 할 수 없는 것이라고 하지만 인범이는 3대 500을 넘기는 몇 안되는 프로그래머 중 한 명이다. 인범이는 BOJ에서 틀린 제출을 할 때마다 턱걸이를 5회 하는 기적의 운동 루틴을 통해 뇌와 근육을 동시에 단련한다. 근육을 단련할 때 식단이 정말로 중요하다는 것을 아는 인범이는 탄수화물이 많은 밥이나 빵 따위의 아침 식사를 대신해 단백질이 많은 계란찜을 해먹는다. 계란찜을 먹기 위해서는 계란을 깨야 하는데, 인범이는 힘이 너무 넘치는 나머지 부엌의 대리석을 이용해 계란을 깨면 늘 껍데기가 산산조각나 뒷처리가 너무 어렵게 되곤 한다. 어떻게 하면 계란을 조심스럽게 깰 수 있을까 고민하던 인범이에게..

1941번: 소문난 칠공주 (BOJ C/C++)

1941번: 소문난 칠공주 사용 언어: C++ 문제 총 25명의 여학생들로 이루어진 여학생반은 5×5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작했다. 곧 모든 여학생이 ‘이다솜파’와 ‘임도연파’의 두 파로 갈라지게 되었으며, 얼마 지나지 않아 ‘임도연파’가 세력을 확장시키며 ‘이다솜파’를 위협하기 시작했다. 위기의식을 느낀 ‘이다솜파’의 학생들은 과감히 현재의 체제를 포기하고, ‘소문난 칠공주’를 결성하는 것이 유일한 생존 수단임을 깨달았다. ‘소문난 칠공주’는 다음과 같은 규칙을 만족해야 한다. 이름이 이름인 만큼, 7명의 여학생들로 구성되어야 한다. 강한 결속력을 위해, 7명의 자리는 서로 가로나 세로로 반..

1759번: 암호 만들기 (BOJ C/C++)

1759번: 암호 만들기 사용 언어: C++ 문제 바로 어제 최백준 조교가 방 열쇠를 주머니에 넣은 채 깜빡하고 서울로 가 버리는 황당한 상황에 직면한 조교들은, 702호에 새로운 보안 시스템을 설치하기로 하였다. 이 보안 시스템은 열쇠가 아닌 암호로 동작하게 되어 있는 시스템이다. 암호는 서로 다른 L개의 알파벳 소문자들로 구성되며 최소 한 개의 모음(a, e, i, o, u)과 최소 두 개의 자음으로 구성되어 있다고 알려져 있다. 또한 정렬된 문자열을 선호하는 조교들의 성향으로 미루어 보아 암호를 이루는 알파벳이 암호에서 증가하는 순서로 배열되었을 것이라고 추측된다. 즉, abc는 가능성이 있는 암호이지만 bac는 그렇지 않다. 새 보안 시스템에서 조교들이 암호로 사용했을 법한 문자의 종류는 C가지가..