문제의 입력을 보면 세로선의 개수는 최대 10개, 높이는 최대 30개이다. 즉 놓치 못하는 규칙을 고려하지 않았을 때 가로선이 있을 수 있는 위치는 총 300개이다. 또 최대 3개의 가로선을 추가할 수 있는 조건을 보았을 때 브루트 포스 알고리즘으로 백트래킹을 사용해도 풀릴 수 있는 문제라고 생각하였다. 따라서 가로선이 놓일 수 있는 부분이 겹치지 않게 놓다보면 시간초과가 발생하지 않을 것이다.
가로선은 세로선에서 오른쪽으로만 놓는다고 생각한다. 따라서 j번 세로선에 놓는다고 했을 때 j-1, j+1의 세로선에 모두 가로선이 존재하지 않아야한다. 만약 j번에 놓을 수 있을 때 dfs를 이용하여 재귀적으로 j번 세로줄부터 놓을 수 있는 위치를 다시 계산한다. 최대한 중복을 줄이기 위해 j번 세로줄부터 확인하는 것이다.
소스 코드
#include <iostream>
#include <string>
#include <cstring>
#include <vector>
#include <deque>
using namespace std;
const int MN = 9;
int N, M, H;
int ans = 4; //최대 3까지이므로 4로 설정
void dfs(int now, int n, bool ladder[31][11]) {
if(n >= ans) return; //이미 최소값을 넘은 경우 탐색하지 않음
bool chk = false; //모두 j번 세로줄이 j번에서 끝나는지 확인하는 변수
for(int j = 1; j <= N; j++) {
int now = j;
for(int i = 1; i <= H; i++) {
if(ladder[i][now-1]) { //왼쪽에 길이 있다면 왼쪽 세로줄로 이동
now--;
}
else if(ladder[i][now]) { //오른쪽에 길이 있다면 오른쪽 세로줄로 이동
now++;
}
}
if(now != j) { //만약 j번에서 끝나지 않은 경우
chk = true; //끝나지 않음을 체크 후 종료
break;
}
}
if(!chk) { //만약 모두 알맞게 끝난 경우
ans = min(ans, n); //최소값 갱신 후 더 이상 탐색하지 않음
return;
}
if(n == 3) return; //3개 가로줄 사용한 경우 리턴
for(int j = now; j < N; j++) { //지금까지 탐색한 세로줄부터
for(int i = 1; i <= H; i++) { //모든 높이를 탐색
if(!ladder[i][j] && !ladder[i][j+1] && !ladder[i][j-1]) { //가로줄을 놓을 수 있는 경우
ladder[i][j] = true; //가로줄 생성
dfs(j, n+1, ladder); //재귀
ladder[i][j] = false; //가로줄 제거
}
}
}
}
int main() {
cin >> N >> M >> H;
bool ladder[31][11];
memset(ladder, 0, sizeof(ladder)); //사다리 초기화
for(int i = 0; i < M; i++) {
int a, b; cin >> a >> b;
ladder[a][b] = true; //가로줄 추가
}
dfs(1, 0, ladder); //재귀로 탐색
if(ans == 4) cout << -1; //방법이 없는 경우 -1출력
else cout << ans;
}
위 과정대로 작성한 코드이다. 방법이 없는 경우를 고려해 초기값을 4로 설정했다. 최대 3까지 정답이 될 수 있기 때문이다.
입력이 string으로 주어진다. 톱니바퀴는 4개로 고정이므로 4개의 입력을 받고 K개의 회전을 입력받는다. 이때 회전하는 톱니의 왼쪽, 오른쪽을 구분하여 계산한다. 알고리즘의 동작 순서는 다음과 같다.
돌리는 톱니의 왼쪽부터 확인한다.
현재 톱니는 돌리는 톱니이다.
만약 맞물리는 부분이 상극인 경우 현재 톱니를 어느 방향으로 돌리는지 배열에 표시하고 왼쪽 톱니가 현재 톱니가 된다.
끝까지 가거나 맞물리는 부분이 상극이 아니어 회전하지 않을 때까지 반복한다.
오른쪽 부분도 같은 과정을 진행한다.
회전하는 방향을 표시해놓은 배열을 보며 톱니를 회전시킨다. 0인 경우 회전하지 않고 1인 경우 시계방향, -1인 경우 반시계방향으로 회전한다.
K번의 회전이 끝난 후 12시에 있는 극이 무엇인지 보고 결과값을 출력한다.
소스 코드
#include <iostream>
#include <string>
#include <cstring>
#include <vector>
#include <deque>
using namespace std;
const int MN = 101;
string wheel[5]; //1~4까지 톱니의 번호
int main() {
cin >> wheel[1] >> wheel[2] >> wheel[3] >> wheel[4]; //4가지 톱니를 입력받음
int K; cin >> K;
int rotation[5]; //회전을 표시하는 배열
for(int i = 0; i < K; i++) {
memset(rotation, 0, sizeof(rotation)); //배열 초기화
int num, direction; cin >> num >> direction;
rotation[num] = direction; //현재 톱니의 회전 방향 체크
//회전하는 톱니 왼쪽
int now = num; //현재 톱니
int nowd = direction; //현재 방향
for(int w = num-1; w > 0; w--) {
if(wheel[now][6] != wheel[w][2]) { //상극인 경우
rotation[w] = -nowd; //반대 방향으로 회전 표시
nowd = -nowd; //현재 방향 수정
now--; //다음 톱니로 이동
}
else { //같은 극인 경우
rotation[w] = 0; //회전하지 않는다고 표시 후 종료
break;
}
}
//회전하는 톱니 오른쪽
now = num; //현재 톱니
nowd = direction; //현재 방향
for(int w = num+1; w <= 4; w++) {
if(wheel[now][2] != wheel[w][6]) { //상극인 경우
rotation[w] = -nowd; //반대 방향으로 회전 표시
nowd = -nowd; //현재 방향 수정
now++; //다음 톱니로 이동
}
else { //같은 극인 경우
rotation[w] = 0; //회전하지 않는다고 표시 후 종료
break;
}
}
//톱니바퀴 회전시키기
for(int j = 1; j <= 4; j++) {
if(rotation[j] == 0) continue; //회전하지 않는 경우 건너뛰기
if(rotation[j] == 1) { //시계방향으로 회전하는 경우
string tmp = wheel[j].substr(0, 7);
wheel[j] = wheel[j][7] + tmp;
}
else if(rotation[j] == -1) { //반시계방향으로 회전하는 경우
string tmp = wheel[j].substr(1);
wheel[j] = tmp + wheel[j][0];
}
}
}
//결과 계산
int ans = 0;
if(wheel[1][0] == '1') ans++;
if(wheel[2][0] == '1') ans +=2;
if(wheel[3][0] == '1') ans += 4;
if(wheel[4][0] == '1') ans += 8;
cout << ans;
}
한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.
준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자.
풀이
문제 설명에 나와 있듯이 유명한 냅색 문제이다. 무게가 정해져 있을 때 가치를 최대로 배낭을 채우는 문제이다. DP문제로 유명한 이 문제는 다음 점화식으로 풀 수 있다.
이 점화식에서 i는 i번째 물건을 뜻한다. j는 무게이다. 즉 dp[i][j]가 뜻하는 것은 i번째 물건을 무게가 j이하로 채울 때 최대 가치의 합을 나타낸다. 따라서 dp[i-1][j]은 i번째 물건을 넣지 않는다는 뜻이고 dp[i-1][j-weight[i]] + cost[i]는 i번째 물건을 넣는다는 것이다. 따라서 i번째 물건의 무게(weight[i])를 j에서 뺀 값에 i번째 물건의 가치(cost[i])를 더한 값을 뜻한다. 즉 위의 점화식이 나타내는 것은 i번째 물건을 넣었을 때와 넣지 않았을 때의 값중 더 큰 값을 저장한다는 것이다. 이 점화식을 이용하여 작성한 코드는 다음과 같다.
소스 코드
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
vector<pair<int,int>> arr;
int dp[101][100001]; //101은 물건의 개수, 100001은 무게의 최대값
int w[101]; //i번째 물건의 무게
int value[101]; //i번째 물건의 가치
int main() {
int N, K; cin >> N >> K;
for(int i = 1; i <= N; i++) {
cin >> w[i] >> value[i];
}
for(int i = 1; i <= N; i++) {
for(int j = 1; j <= K; j++) {
if(j < w[i]) //j값보다 i번째 물건의 무게가 더 큰 경우 배낭에 넣을 수 없다.
dp[i][j] = dp[i-1][j]; //따라서 물건을 넣지 않는다.
else { //물건이 들어갈 경우
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + value[i]);
//물건을 넣는 경우와 넣지 않은 경우 중 더 큰 가치 선택
}
}
}
cout << dp[N][K];
}
이렇게 문제를 풀 경우 상당한 메모리가 소모도니다. 이 코드를 보면 i번째 dp배열은 i-1번째 dp배열로부터 계산되는 것을 알 수 있다. i값은 2가지만 사용한다. 또 j번 인덱스만 봤을 때 더 큰 값이거나 같은 값으로 유지된다. 그림으로 나타내면 다음과 같다.
그렇다면 1개의 배열로 사용할 수 있지 않을까? 만약 j를 큰 값부터 줄여간다면 작은 값들에 영향을 주지 않고 갱신할 수 있을 것이다 (큰 값부터 한다는 것은 만약 작은 값에서 j-w[i]와 같이 큰 값으로 갱신 된다면 이후에 큰 값을 갱신할 때 이미 영향을 받은 값을 다시 갱신할 수 있기 때문이다). 코드로 나타내면 다음과 같다.
소스 코드
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
const int MN = 101;
const int MK = 100101;
int w[MN], cost[MN];
int dp[MK]; //1차원 배열
int main() {
int N, K; cin >> N >> K;
for(int i = 1; i <= N; i++) {
cin >> w[i] >> cost[i];
}
for(int i = 1; i <= N; i++) {
for(int j = K; j >= 0; j--) { //큰 값부터 작은 값으로
if(j >= w[i]) //배낭에 넣을 수 있을 때만
dp[j] = max(dp[j], dp[j-w[i]] + cost[i]); //더 큰 값으로 갱신
}
}
cout << dp[K];
}
채점 결과
위의 결과가 1차원 배열을 사용한 경우가 아래 결과가 2차원 배열을 사용한 경우이다. 메모리가 거의 20배 차이 나는 것을 알 수 있다.
문자열과 놀기를 세상에서 제일 좋아하는 영식이는 오늘도 문자열 2개의 LCS(Longest Common Subsequence)를 구하고 있었다. 어느 날 영식이는 조교들이 문자열 3개의 LCS를 구하는 것을 보았다. 영식이도 도전해 보았지만 실패하고 말았다.
이제 우리가 할 일은 다음과 같다. 영식이를 도와서 문자열 3개의 LCS를 구하는 프로그램을 작성하라.
풀이
우리가 문자열 2개의 LCS를 구할 때 2차원 dp배열을 이용했다. 이 문제는 정말 단순하게 dp배열을 3차원으로만 늘리면 쉽게 풀린다. 3개의 문자열 s1, s2, s3가 있을 때 각각 i, j, k번 문자가 같을 경우 i, j, k번 이전의 문자열까지 중에 가장 큰 공통 부분 문자열의 크기에 1을 더한다. 그렇지 않을 경우 각각 i-1, j-1, k-1번까지의 공통 부분 문자열의 최대 크기를 저장한다. 코드로 나타내면 다음과 같다.
소스 코드
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
const int MN = 101;
int dp[MN][MN][MN];
int max(int a, int b, int c) { //인자 3개짜리 최대값 함수
return max(max(a, b), c);
}
int main() {
string s1, s2, s3;
cin >> s1 >> s2 >> s3; //3개의 문자열 입력
s1 = ' ' + s1;
s2 = ' ' + s2;
s3 = ' ' + s3;
for(int i = 1; i < s1.size(); i++) {
for(int j = 1; j < s2.size(); j++) {
for(int k = 1; k < s3.size(); k++) {
if(s1[i] == s2[j] && s2[j] == s3[k]) { //3개 문자가 모두 같은 경우
dp[i][j][k] = dp[i-1][j-1][k-1] + 1; //이전 공통 부분 문자열 크기에 1을 더함
}
else { //같지 않은 경우
dp[i][j][k] = max(dp[i-1][j][k], dp[i][j-1][k], dp[i][j][k-1]); //지금까지의 최대값 저장
}
}
}
}
cout << dp[s1.size()-1][s2.size()-1][s3.size()-1];
}
팰린드롬이란 대칭 문자열이다. 즉, 왼쪽에서 오른쪽으로 읽었을때와 오른쪽에서 왼쪽으로 읽었을때 같다는 얘기다. 당신은 문자열이 주어졌을때, 최소 개수의 문자를 삽입하여 팰린드롬이 되게 되는 문자의 개수를 구하는 프로그램을 작성하여라.
예제에서는, 2개의 문자를 삽입하여 팰린드롬이 된다. "Ab3bd"는 "dAb3bAd" 혹은 "Adb3bdA" 로 바뀔 수 있다. 하지만, 2개 미만의 문자를 삽입해서는 팰린드롬이 될 수 없다.
풀이
이 문제는 LCS문제를 변형한 문제이다. 한 문자열이 펠린드롬이 되기 위해서는 펠린드롬이 되는 부분 문자열에 부족한 부분을 추가하면 된다. 따라서 어떤 문자열과 그 문자열을 뒤집은 문자열의 공통 부분 문자열의 길이를 구하고 원래 문자열과의 차이를 구하면 된다. 예시는 다음과 같다.
ab3bd를 뒤집으면 db3ba가 된다. 그럼 ab3bd와 db3ba의 공통 부분 문자열은 b3b가 된다. 그렇다면 원래 문자에서 빠진 문자는 a와 d가 있다. 이 a와 d를 원래 문자열에 하나씩 추가하면 펠린드롬을 만들 수 있는 것이다. 코드로 나타내면 다음과 같다.
소스 코드
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
const int MN = 5001;
int dp[MN][MN]; //LCS를 위한 dp배열
int main() {
int answer = 0;
int N; cin >> N;
string s1, s2; //원래 문자열과 뒤집은 문자열
cin >> s1;
s2 = s1;
s1 = ' ' + s1;
reverse(s2.begin(), s2.end()); //문자열 뒤집기
s2 = ' ' + s2;
for(int i = 1; i < s1.size(); i++) { //공통 부분 문자열 길이 구하기
for(int j = 1; j < s2.size(); j++) {
if(s1[i] == s2[j]) {
dp[i][j] = dp[i-1][j-1] + 1;
answer = max(answer, dp[i][j]);
}
else {
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
}
}
}
cout << N - dp[N][N]; //공통 부분 문자열의 길이를 원래 문자열 길이에서 뺀다. 즉 부족한 문자 개수 출력
}
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.
예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.
풀이
LCS문제는 DP를 이용한다. 2차원 배열 DP에서 dp[i][j]가 의미하는 것은 두 문자열 s1, s2에 대하여 s1의 i번째 문자와 s2의 j번째 문자까지 공통되는 부분 수열의 길이를 나타낸다. 배열은 다음과 같다.
만약 s1[i]와 s2[j]가 같다면 dp[i-1][j-1]에 1을 더한 값을 넣는다. 이전 길이에서 하나 더 늘어났기 때문이다. 그렇지 않고 만 약 s1[i]와 s2[j]가 같지 않다면 dp[i-1][j]와 dp[i][j-1] 중에 더 큰 값을 넣는다. 이전 문자까지 이루어진 공통 부분 수열 중 가장 큰 값을 넣어야하기 때문이다. 코드를 짜면 다음과 같다.
소스 코드
#include <iostream>
#include <string>
#include <vector>
#include <deque>
using namespace std;
const int MN = 1001;
int dp[MN][MN];
int main() {
string s1, s2; //두 문자열
cin >> s1 >> s2;
s1 = ' ' + s1; //1번 인덱스부터 사용하기 위해 앞에 공백을 추가
s2 = ' ' + s2;
for(int i = 1; i < s1.size(); i++) {
for(int j = 1; j < s2.size(); j++) {
if(s1[i] == s2[j]) //같은 경우
dp[i][j] = dp[i-1][j-1] + 1; //이전 문자까지 중에 가장 큰 값에 1을 추가
else //같지 않을 경우
dp[i][j] = max(dp[i-1][j], dp[i][j-1]); //이전 문자까지 중 가장 큰 값으로 설정
}
}
cout << dp[s1.size()-1][s2.size()-1];
}
앞에 공백을 추가하는 이유는 1번 인덱스부터 사용하기 위해서이다. 대각선 값을 가져오는데 만약 첫 문자가 같은 경우 -1이 되므로 (1, 1)부터 인덱스를 시작하기 위하여 앞에 공백을 넣었다.
