개발 블로그

문제 링크 : https://www.acmicpc.net/problem/1062

문제

남극에 사는 김지민 선생님은 학생들이 되도록이면 많은 단어를 읽을 수 있도록 하려고 한다. 그러나 지구온난화로 인해 얼음이 녹아서 곧 학교가 무너지기 때문에, 김지민은 K개의 글자를 가르칠 시간 밖에 없다. 김지민이 가르치고 난 후에는, 학생들은 그 K개의 글자로만 이루어진 단어만을 읽을 수 있다. 김지민은 어떤 K개의 글자를 가르쳐야 학생들이 읽을 수 있는 단어의 개수가 최대가 되는지 고민에 빠졌다.

남극언어의 모든 단어는 "anta"로 시작되고, "tica"로 끝난다. 남극언어에 단어는 N개 밖에 없다고 가정한다. 학생들이 읽을 수 있는 단어의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문자로만 이루어져 있고, 길이가 8보다 크거나 같고, 15보다 작거나 같다. 모든 단어는 중복되지 않는다.

출력

첫째 줄에 김지민이 K개의 글자를 가르칠 때, 학생들이 읽을 수 있는 단어 개수의 최댓값을 출력한다.

접근 방법

int형은 4byte( = 32bit) 이므로 0부터 (2^32 - 1)까지 표현할 수 있다. 

여기서 알파벳은 총 26개이므로 0번비트부터 25번 비트까지만 사용하므로 int 형 내에서 커버가능하다.

먼저 N개의 단어를 입력받는데, 이때 단어를 이루고 있는 알파벳을 체크해서 word[]에 비트마스크로 표시한다. 

ex) 0번째 단어가 "antarctica"라고 하면, 이 단어를 이루고 있는 알파벳 [a,c,i,n,r,t]를 아래와 같이 비트로 표현해서 word[0]에 저장한다.

그 다음으로 K의 값을 따진다.

case 1) 5보다 작으면 N개 단어 모두 읽지 못하게 될 것이다. 왜냐하면 N개의 단어들 중에 최대한 많이 읽어야 하는데, 각 단어는 무조건 "a,n,t,i,c"가 포함된다고 했기 때문이다.

case 2) 만약 K가 26이면 모든 알파벳을 알고 있으므로 N개의 단어 모두 읽을 수 있다.

case 3) K가 5도 아니고 26도 아니면 chcked 변수를 초기화한뒤 DFS()를 호출한다.

cheked 변수는 이때까지 배운 알파벳들을 비트로 표현한 것이다.

DFS()에서는 완전탐색으로 26개의 알파벳 중에 K-5개를 선택하는 모든 경우를 따지게 된다. 단, 시간복잡도를 줄이기 위해 start 파라미터를 이용해서 중복조합을 구했다. (a,b를 선택하는 경우나 b,a를 선택하는 경우나 같기 때문이다.)

toPick이 0이 되면, 즉 배워야할 알파벳을 다 선택했으면, 그 알파벳들로 읽을 수 있는 단어가 N개 중 몇개인지 카운트한다. 

알파벳을 선택하는 조합을 바꿀 때마다 "읽을 수 있는 단어 수의 최대값"을 갱신한다. 

모든 경우를 따진 뒤 최대값을 출력한다.

//
//  비트_BOJ1062_가르침.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/07/07.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int checked;
int word[50];   //N 최대 50개
int N, K;

int maxi = 0;

void DFS(int toPick, int start, int checked){    //증복조합
    
    if(toPick==0){  //배울 알파벳 골랐으면
        
        //그 알파벳들로 N개 단어 중 몇개 읽을 수 있는지 카운트해서 최대값 찾기
        int cnt = 0;
        for(int i = 0; i<N ;i++){
            if((word[i] & checked) == word[i]) cnt++;
        }
        if(maxi < cnt) maxi = cnt;
        return;
    }

    for(int i = start; i<26; i++){
        if((checked & (1<<i)) == 0){   //방문 안 한 경우에만
            checked |= (1<<i);
            DFS(toPick-1, i, checked);
            checked &= ~(1<<i);
        }
        
    }
}

int main(){
    
    cin >> N >> K;
    
    string str;
    for(int i = 0; i<N; i++){
        cin >> str;
        
        int num = 0;
        for(int j = 0; j<str.length(); j++){
            num |= 1 << (str[j] - 'a');
        }
        word[i] = num;
    }
    
    if(K<5) cout << 0;  //anta ~ tica 읽으려면 최소 a,n,t,i,c 5개 이상은 알고 있어야함
    else if (K==26) cout << N;
    else{
        
        //a, n, t, i, c 를 이미 알고 있음을 초기화.
        checked |= 1 << ('a'-'a');
        checked |= 1 << ('n'-'a');
        checked |= 1 << ('t'-'a');
        checked |= 1 << ('i'-'a');
        checked |= 1 << ('c'-'a');
        
        DFS(K-5, 0, checked);
        cout << maxi;
    }
 
    return 0;
}

문제 링크 : https://www.acmicpc.net/problem/3040

문제

매일 매일 일곱 난쟁이는 광산으로 일을 하러 간다. 난쟁이가 일을 하는 동안 백설공주는 그들을 위해 저녁 식사를 준비한다. 백설공주는 의자 일곱개, 접시 일곱개, 나이프 일곱개를 준비한다.

어느 날 광산에서 아홉 난쟁이가 돌아왔다. (왜 그리고 어떻게 아홉 난쟁이가 돌아왔는지는 아무도 모른다) 아홉 난쟁이는 각각 자신이 백설공주의 일곱 난쟁이라고 우기고 있다.

백설공주는 이런 일이 생길 것을 대비해서, 난쟁이가 쓰고 다니는 모자에 100보다 작은 양의 정수를 적어 놓았다. 사실 백설 공주는 공주가 되기 전에 매우 유명한 수학자였다. 따라서, 일곱 난쟁이의 모자에 쓰여 있는 숫자의 합이 100이 되도록 적어 놓았다.

아홉 난쟁이의 모자에 쓰여 있는 수가 주어졌을 때, 일곱 난쟁이를 찾는 프로그램을 작성하시오. (아홉 개의 수 중 합이 100이 되는 일곱 개의 수를 찾으시오)

입력

총 아홉개 줄에 1보다 크거나 같고 99보다 작거나 같은 자연수가 주어진다. 모든 숫자는 서로 다르다. 또, 항상 답이 유일한 경우만 입력으로 주어진다.

출력

일곱 난쟁이가 쓴 모자에 쓰여 있는 수를 한 줄에 하나씩 출력한다.

접근 방법

DFS 를 이용해서 9명 중 7명을 뽑았을 때 난쟁이 번호의 합이 100이 되는지 검사한다. 정답을 찾으면 true 를 리턴해서 DFS를 빠져나왔을 때 탐색을 진행하지 않고 종료한다.

좀 더 시간을 줄이기 위해 DFS의 첫번째 파라미터를 이용해서 중복 조합으로 난쟁이들을 뽑았다. 두명을 뽑는다고 했을 때, (1번 난쟁이, 2번 난쟁이)를 뽑는 것과 (2번 난쟁이, 1번 난쟁이) 를 뽑는 것이 같기 때문이다.

import java.util.*;
public class DFS_BOj3040_백설공주와일곱난쟁이 {

	static int[] numArr, visited;
	static ArrayList<Integer> ansList = new ArrayList<Integer>(); 
	
	public static boolean DFS(int start, int toPick, int sum) {
		if(toPick==0 && sum==100) {
			for(int i = 0; i<ansList.size(); i++) {
				System.out.println(ansList.get(i));
			}
			return true;
		}
		
		for(int i = start; i<9; i++) {
			if(visited[i] == 0) {
				visited[i] = 1;
				ansList.add(numArr[i]);
				if(DFS(i, toPick-1, sum + numArr[i])==false) {
					ansList.remove(ansList.size()-1);
					visited[i] = 0;
				}
				else break;
			}
		}
		return false;
	}
	
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		numArr = new int[9];
		visited = new int[9];
		
		for(int i = 0; i<9; i++) {
			numArr[i] = sc.nextInt();
		}
		
		DFS(0,7,0);	
	}
}

문제 링크 : https://www.acmicpc.net/problem/16937

문제

크기가 H×W인 모눈종이와 스티커 N개가 있다. i번째 스티커의 크기는 Ri×Ci이다. 모눈종이는 크기가 1×1인 칸으로 나누어져 있으며, 간격 1을 두고 선이 그어져 있다.

오늘은 모눈종이에 스티커 2개를 붙이려고 한다. 스티커의 변은 격자의 선과 일치하게 붙여야 하고, 두 스티커가 서로 겹치면 안 된다. 단, 스티커가 접하는 것은 가능하다. 스티커를 90도 회전시키는 것은 가능하다. 스티커가 모눈종이를 벗어나는 것은 불가능하다.

두 스티커가 붙여진 넓이의 최댓값을 구해보자.

입력

첫째 줄에 모눈종이의 크기 H, W, 둘째 줄에 스티커의 수 N이 주어진다. 다음 N개의 줄에는 스티커의 크기 Ri, Ci가 주어진다.

출력

첫째 줄에 두 스티커가 붙여진 넓이의 최댓값을 출력한다. 두 스티커를 붙일 수 없는 경우에는 0을 출력한다.

제한

• 1 ≤ H, W, N ≤ 100
• 1 ≤ Ri, Ci ≤ 100

접근 방법

N개의 스티커 중 DFS 함수를 이용해 2개를 고른다. 이 때 중복 조합을 이용해 중복을 제거한다.

고른 2개의 스티커에 대해 총 4가지 경우를 따져서 스티커를 붙일 수 있는지 검사해야한다.

1) 둘 다 그대로

2) 1번 스티커만 회전

3) 2번 스티커만 회전

4) 둘 다 회전

각 경우에 대해 위 아래로 붙였을 때와 좌우로 붙였을 때 모두 검사해서 하나라도 모눈종이 안에 들어온다면 스티커 두개 넓이를 계산한다.

import java.util.*;

class Pair16937{
	Integer h, w;
	public Pair16937(Integer _h, Integer _w) {
		this.h = _h;
		this.w = _w;
	}
	public Integer getHeight() {
		return this.h;
	}
	public Integer getWidth() {
		return this.w;
	}
}

public class BF_BOJ16937_두스티커 {
	
	static int H, W, N;
	static int[] visited = new int[100];
	static ArrayList<Pair16937> pairList = new ArrayList<Pair16937>();
	static ArrayList<Pair16937> tmpList = new ArrayList<Pair16937>();
	static int maxi = 0;
	
	static boolean chkHeight(int h1, int w1, int h2, int w2) {		//위 아래로 붙였을 때 
		if(h1+h2 > H || Math.max(w1, w2) > W) return false;
		else return true;
	}
	static boolean chkWidth(int h1, int w1, int h2, int w2) {		//양옆으로 붙였을 때 
		if(Math.max(h1, h2) > H || w1 + w2 > W) return false;
		else return true;
	}
	
	static boolean chkHW(int h1, int w1, int h2, int w2) {
		if(chkHeight(h1,w1,h2,w2)==true || chkWidth(h1,w1,h2,w2)==true) return true;
		else return false;
	}
	
	
	static void DFS(int toPick, int start) {
		
		if(toPick==0) {
			int h1 = tmpList.get(0).getHeight();
			int w1 = tmpList.get(0).getWidth();
			
			int h2 = tmpList.get(1).getHeight();
			int w2 = tmpList.get(1).getWidth();
			
			//1번 그대로, 2번 그대로 
			boolean chk = false;
			if(chkHW(h1,w1,h2,w2) == true) {	
				int area = h1*w1 + h2*w2;
				if(maxi<area) maxi = area;
				chk = true;
			}
			else {
				for(int i = 0; i<3; i++) {
					int a,b,c,d;
					if(i==0) {				//1번 회전, 2번 그대로
						a = w1; b = h1;
						c = h2; d = w2;
					}
					else if(i==1) {			//1번 그대로, 2번 회전
						a = h1; b = w1;
						c = w2; d = h2;
					}
					else {					//1번 회전, 2번 회전 
						a = w1; b = h1;
						c = w2; d = h2;
					}
					if(chkHW(a,b,c,d)==true) {
						chk = true;
						int area = h1*w1 + h2*w2;
						if(maxi<area) maxi = area;
						return;
					}
				}
			}
			
			return;
		}
		
		for(int i = start; i<pairList.size(); i++) {
			
			if(visited[i]==0) {
				visited[i] = 1;
				tmpList.add(pairList.get(i));
				DFS(toPick-1, i);
				tmpList.remove(tmpList.size()-1);
				visited[i] = 0;
			}
		}
	}
	
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		H = sc.nextInt();
		W = sc.nextInt();
		N = sc.nextInt();
		for(int i = 0; i<N; i++) {
			int h = sc.nextInt();
			int w = sc.nextInt();
			pairList.add(new Pair16937(h,w));
		}
		
		DFS(2,0);
		
		System.out.print(maxi);
	}
}

문제 링크 : www.acmicpc.net/problem/15686

문제

크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸, 왼쪽에서부터 c번째 칸을 의미한다. r과 c는 1부터 시작한다.

이 도시에 사는 사람들은 치킨을 매우 좋아한다. 따라서, 사람들은 "치킨 거리"라는 말을 주로 사용한다. 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다. 즉, 치킨 거리는 집을 기준으로 정해지며, 각각의 집은 치킨 거리를 가지고 있다. 도시의 치킨 거리는 모든 집의 치킨 거리의 합이다.

임의의 두 칸 (r1, c1)과 (r2, c2) 사이의 거리는 |r1-r2| + |c1-c2|로 구한다.

예를 들어, 아래와 같은 지도를 갖는 도시를 살펴보자.

0은 빈 칸, 1은 집, 2는 치킨집이다.

(2, 1)에 있는 집과 (1, 2)에 있는 치킨집과의 거리는 |2-1| + |1-2| = 2, (5, 5)에 있는 치킨집과의 거리는 |2-5| + |1-5| = 7이다. 따라서, (2, 1)에 있는 집의 치킨 거리는 2이다.

(5, 4)에 있는 집과 (1, 2)에 있는 치킨집과의 거리는 |5-1| + |4-2| = 6, (5, 5)에 있는 치킨집과의 거리는 |5-5| + |4-5| = 1이다. 따라서, (5, 4)에 있는 집의 치킨 거리는 1이다.

이 도시에 있는 치킨집은 모두 같은 프랜차이즈이다. 프렌차이즈 본사에서는 수익을 증가시키기 위해 일부 치킨집을 폐업시키려고 한다. 오랜 연구 끝에 이 도시에서 가장 수익을 많이 낼 수 있는  치킨집의 개수는 최대 M개라는 사실을 알아내었다.

도시에 있는 치킨집 중에서 최대 M개를 고르고, 나머지 치킨집은 모두 폐업시켜야 한다. 어떻게 고르면, 도시의 치킨 거리가 가장 작게 될지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N(2 ≤ N ≤ 50)과 M(1 ≤ M ≤ 13)이 주어진다.

둘째 줄부터 N개의 줄에는 도시의 정보가 주어진다.

도시의 정보는 0, 1, 2로 이루어져 있고, 0은 빈 칸, 1은 집, 2는 치킨집을 의미한다. 집의 개수는 2N개를 넘지 않으며, 적어도 1개는 존재한다. 치킨집의 개수는 M보다 크거나 같고, 13보다 작거나 같다.

출력

첫째 줄에 폐업시키지 않을 치킨집을 최대 M개를 골랐을 때, 도시의 치킨 거리의 최솟값을 출력한다.

접근 방법

1) 기본 DFS + 기본 BFS -> 시간 초과

처음에는 DFS로 치킨 집 중 M개를 선택하고, 선택이 완료되면 BFS로 각 집에서 치킨집까지 최소 거리를 구했다. 그랬더니 답은 제대로 나왔지만 시간 초과가 떴다.

2) 기본 DFS + BFS 사용x -> 시간 초과

M의 최대가 13밖에 안되니 BFS 대신 직접 각 집에서 치킨집까지 거리를 abs()를 이용해서 구했다.

3) 중복조합으로 DFS 개선 + BFS 사용x -> 통과

치킨 집을 2개 선택한다 했을 때, <1번, 2번> 이나 <2번, 1번>이나 같으므로 중복 조합을 이용했다.

//
//  BF_BOJ15686_치킨배달.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/04/11.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <string.h>
#include <queue>
#include <cmath>
using namespace std;

int N, M;

int map[51][51];
int fromStart[51][51];
int newMap[51][51];
vector<pair<int,int>> homeVec;       //1
vector<pair<int,int>> chickenVec;   //2
int visited[100] = {0};
vector<pair<int,int>> pickedChick;   //2중 M개 선택

//위 오 아 왼
int dr[4] = {-1,0,1,0};
int dc[4] = {0,1,0,-1};
int mini = 100000000;
int answer =100000000;


void pickChickDFS(int toPick, int start){

    if(toPick==0){
        
        int sum=0;
        //각 집에서 pickChick까지의 거리들 중 최소값들의 합
        for(int i = 0; i<homeVec.size();i++){
            mini = 100000000;
            
            for(int j = 0; j<pickedChick.size(); j++){
                int dis = abs(homeVec[i].first-pickedChick[j].first)
                + abs(homeVec[i].second - pickedChick[j].second);
                
                if(mini>dis) mini = dis;
            }
            sum+=mini;
            if(sum>answer) return;
        }
        
        if(answer>sum) answer = sum;
        return;
    }
    
    for(int i = start; i<chickenVec.size(); i++){
        if(visited[i]==0){
            visited[i] = 1;
            pickedChick.push_back(chickenVec[i]);
            pickChickDFS(toPick-1, i);
            pickedChick.pop_back();
            visited[i] = 0;
        }
    }
}


int main(){
    cin >> N >> M;
    
    for(int i = 1; i<=N; i++){
        for(int j = 1; j<=N; j++){
            cin >> map[i][j];
            if(map[i][j]==1){   homeVec.push_back(make_pair(i,j)); }
            if(map[i][j]==2){   chickenVec.push_back(make_pair(i,j)); }
        }
    }
    
    pickChickDFS(M, 0);
    cout << answer;
    
    return 0;
}

문제 링크 : www.acmicpc.net/problem/16922

문제

로마 숫자에서는 수를 나타내기 위해서 I, V, X, L을 사용한다. 각 문자는 1, 5, 10, 50을 의미하고, 이 문제에서 다른 문자는 사용하지 않는다.

하나 또는 그 이상의 문자를 이용해서 수를 나타낼 수 있다. 문자열이 나타내는 값은, 각 문자가 의미하는 수를 모두 합한 값이다. 예를 들어, XXXV는 35, IXI는 12를 의미한다.

실제 로마 숫자에서는 문자의 순서가 중요하지만, 이 문제에서는 순서는 신경쓰지 않는다. 예를 들어, 실제 로마 숫자에서 IX는 9를 의미하지만, 이 문제에서는 11을 의미한다.

로마 숫자를 N개 사용해서 만들 수 있는 서로 다른 수의 개수를 구해보자.

입력

첫째 줄에 사용할 수 있는 문자의 개수 N (1 ≤ N ≤ 20)이 주어진다.

출력

첫째 줄에 로마 숫자 N개를 사용해서 만들 수 있는 서로 다른 수의 개수를 출력한다.

접근 방법

완전탐색 문제라 모든 경우의 수에 대해 DFS 로 풀었는데 시간 초과가 떴다.

문제의 조건에서 순서를 상관하지 않으므로 IIX = XII 이다. 이는 중복 조합으로 해결할 수 있다.

중복조합은 서로 다른 n개 중 k 개를 뽑는 경우인데, 여기서는 서로 다른 4개(I,V,X,L) 개 중 중복을 허용하고 순서 상관 없이 N개를 뽑는것이다.

DFS() 안의 반복문을 보자.

시작 값을 변화시킴으로써 중복 조합을 구현할 수 있다. i의 변화 값은 다음과 같다. (4개만 나타냄)

(앞에 -가 붙은 경우는 시작 값을 i=0으로 고정시켰을 경우에 나오는 경우이다. 시작 값을 변화시킴으로써 IIX = XII 처럼 같은 수를 나타내는 경우 한번만 카운트 할 수 있다.)

0 0 0 0

0 0 0 1

0 0 0 2

0 0 0 3

- 0 0 1 0

0 0 1 1

0 0 1 2

0 0 1 3

- 0 0 2 0

- 0 0 2 1

0 0 2 2

0 0 2 3

- 0 0 3 0

- 0 0 3 1

- 0 0 3 2

0 0 3 3

...

//
//  BF_BOJ16922_로마숫자만들기.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/04/03.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

#define I 1
#define V 5
#define X 10
#define L 50

int N;
int answer = 0;
int sum = 0;
bool visited[1001] = {0};
char cArr[4] = {'I','V','X','L'};
int iArr[4] = {1,5,10,50};

vector<int> sumVec;
vector<string> strVec;
string str = "";
void pickDFS(int toPick, int start, int s){
    
    
    if(toPick==0){
        if(visited[s]==false){
            answer++;
            visited[s]=true;
        }
        return;
    }
    
    for(int i = start; i<4; i++){				//시작점을 바꿔서 중복 조합 구현 가능
        pickDFS(toPick-1, i, s+iArr[i]);
    }
    
}


int main(){
    cin>>N;
    pickDFS(N, 0, 0);
    cout << answer;
    
    return 0;
}