https://www.acmicpc.net/problem/2961 2961번: 도영이가 만든 맛있는 음식 첫째 줄에 재료의 개수 N(1 ≤ N ≤ 10)이 주어진다. 다음 N개 줄에는 그 재료의 신맛과 쓴맛이 공백으로 구분되어 주어진다. 모든 재료를 사용해서 요리를 만들었을 때, 그 요리의 신맛과 쓴맛은 www.acmicpc.net 신맛과 쓴맛이 최대한 비슷해지게 만드는 문제. N이 10으로 매우 작아서 O(2^N) 시간복잡도를 가지는 브루트포스로도 문제를 해결할 수 있다. 해당 문제의 구현 방법으로는 재귀함수를 사용한 구현과(dfs-like) 비트마스킹을 이용한 구현이 있는데, 비트마스킹을 연습하기에 나쁘지 않은 유형이지 싶어서 비트마스킹으로 풀어보았다. i번 재료를 섞는 경우에 i번 비트를 1로 켜고..

https://www.acmicpc.net/problem/16173 16173번: 점프왕 쩰리 (Small) 쩰리는 맨 왼쪽 위의 칸에서 출발해 (행, 열)로 나타낸 좌표계로, (1, 1) -> (2, 1) -> (3, 1) -> (3, 3)으로 이동해 게임에서 승리할 수 있다. www.acmicpc.net https://www.acmicpc.net/problem/16174 16174번: 점프왕 쩰리 (Large) 쩰리는 맨 왼쪽 위의 칸에서 출발해 (행, 열)로 나타낸 좌표계로, (1, 1) -> (2, 1) -> (3, 1) -> (3, 3)으로 이동해 게임에서 승리할 수 있다. www.acmicpc.net BFS 문제. bfs를 함에 있어서 위치에 따라 이동거리가 바뀐다는 점에 유의해서 작성해주면 ..

https://www.acmicpc.net/problem/3758 3758번: KCPC 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 테스트 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫 번째 줄에는 www.acmicpc.net 정렬 문제. 점수가 높은 팀 문제 제출 횟수가 적은 팀 마지막 제출 시간이 더 빠른 팀 순서대로 정렬해주면 되는 문제. 이것저것 관리하기 귀찮으므로 구조체를 사용했다. N이 별로 크지 않으므로 직접 비교해서 N^2 정렬을 해줘도 좋다만 sort 함수의 정렬순서를 바꾸는 비교함수를 직접 작성해보는 연습용 문제로써 나쁘지 않은듯. struct solve{ int cnt = 0; int time = 0; in..

https://www.acmicpc.net/problem/2942 2942번: 퍼거슨과 사과 맨체스터 유나이티드의 감독 퍼거슨은 빨간 사과를 R개, 초록 사과를 G개 가지고 있다. 훈련장에 있는 선수들 중 몇 명에게 나누어 주려고 한다. 단, 선수들이 서로 같은 개수의 사과를 받지 못하 www.acmicpc.net 입력으로 들어오는 R과 G의 범위가 넓어서 for문으로 R,G 이하의 모든 수에 대해서 탐색하면 시간초과를 받게 될 수 있다. 시간을 절약하기 위해서 R과 G의 최대공약수를 찾아서 그 최대공약수의 약수를 찾는 방식으로 접근하면 조금 더 빠르게 풀 수 있다. R과 G가 10억에 가까운 임의의 수 두개라면 이런경우에도 TLE가 나지 싶은데 테스트케이스가 그리 빡빡하지는 않은듯..? #include..

https://www.acmicpc.net/problem/11123 11123번: 양 한마리... 양 두마리... 얼마전에 나는 불면증에 시달렸지... 천장이 뚫어져라 뜬 눈으로 밤을 지새우곤 했었지. 그러던 어느 날 내 친구 광민이에게 나의 불면증에 대해 말했더니 이렇게 말하더군. "양이라도 세봐!" www.acmicpc.net 그래프 순회 문제입니다. #으로 연결된 묶음들을 한 덩어리로 볼때 덩어리의 갯수를 세서 출력해주는 문제입니다. 입력 방식이 다를 뿐 기본적으로 1012 유기농 배추와 다르지 않습니다. DFS 사용해서 해결했습니다. #include using namespace std; string s[123]; bool vis[123][123] = {0}; int dx[] = {1,-1,0,0}..

https://www.acmicpc.net/problem/15312 15312번: 이름 궁합 영어 대문자 알파벳 26개의 획수는 순서대로 3, 2, 1, 2, 3, 3, 2, 3, 3, 2, 2, 1, 2, 2, 1, 2, 2, 2, 1, 2, 1, 1, 1, 2, 2, 1 로 정한다. (출제자가 알파벳 대문자를 쓰는 방법이 기준이다) www.acmicpc.net 구현 문제. 두 이름의 길이가 같음이 보장되기 때문에, 상대적으로 쉽게 해결할 수 있는 문제이다. 힌트로 주어지는 영어 대문자 알파벳의 획수를 배열등에 넣고 관리해줘야 한다. v.push_back(line[A[i]-'A']); 여기에서처럼 알파벳을 인덱스에 매칭시킬때 'A', 'a' 등을 빼주면 아스키코드 65 ~ 90번에 매칭된 대문자는 0~..

https://www.acmicpc.net/problem/16435 16435번: 스네이크버드 첫 번째 줄에 과일의 개수 N (1 ≤ N ≤ 1,000) 과 스네이크버드의 초기 길이 정수 L (1 ≤ L ≤ 10,000) 이 주어집니다. 두 번째 줄에는 정수 h1, h2, ..., hN (1 ≤ hi ≤ 10,000) 이 주어집니다. www.acmicpc.net 그리디 문제. 스네이크버드보다 높이가 작은 과일들을 먹는데에는 아무런 제한이 없기 때문에, 높이가 작은 과일들을 먼저 먹지 않을 이유가 없다. 입력으로 들어온 $h_i$를 정렬해서 작은순으로 먹게 하면 된다. #include using namespace std; vector v; int main(){ int N,M,k; cin >> N >> M;..

https://www.acmicpc.net/problem/18511 재귀함수를 활용하는 문제. 3^9 = 19683 으로 그렇게 큰 범위의 숫자가 아니기 때문에 K를 선택해서 수를 구성하는 모든 경우의 수를 직접 탐색해봐도 시간초과 없이 문제를 해결할 수 있다. 재귀함수를 사용하는게 일반적이고 깔끔한 풀이이다. 재귀함수를 사용한 탐색 도중에 N의 범위를 넘어가는 경우 음수(-1) 등을 반환하도록 처리해주면 된다. #include using namespace std; int N,M; vector K; int recur(int val){ if(val > N) return -1; int ans = val; for(auto k : K){ ans = max(ans, recur(val*10 + k)); } retu..

구현 문제. https://www.acmicpc.net/problem/1337 1337번: 올바른 배열 첫째 줄에 배열의 크기 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 배열의 원소가 한 줄에 하나씩 주어진다. 원소는 1,000,000,000보다 작거나 같은 음이 아닌 정수이 www.acmicpc.net O(5N) 등의 다양한 풀이가 있는듯 한데, 나는 O(N^2) 풀이를 구상했고 이걸로 구현해서 정답을 받았다. 일단 입력으로 주어진 배열을 정렬한 다음에, 두 인덱스 i와 j ( i < j ) 를 잡는다. 해당 인덱스에 있는 배열 값의 차는 v[i] - v[j] 이고, 해당 인덱스 구간에 있는 배열 값의 갯수는 i-j+1이다. 추가해야할 원소를 최소로 만들기 위해서 ..

https://www.acmicpc.net/problem/17087 17087번: 숨바꼭질 6 수빈이는 동생 N명과 숨바꼭질을 하고 있다. 수빈이는 현재 점 S에 있고, 동생은 A1, A2, ..., AN에 있다. 수빈이는 걸어서 이동을 할 수 있다. 수빈이의 위치가 X일때 걷는다면 1초 후에 X+D나 X-D로 이 www.acmicpc.net 최대공약수를 이용하는 문제. 각 동생의 위치 $A_i$ 에 대해서 수빈이와의 거리 $dir_i$ 를 계산한다. $dir_i$ 거리를 이동하는 방법으로, 수빈이는 한번에 D만큼만 이동할 수 있기 때문에 $dir_i$ 의 약수가 D이면 수빈이가 동생을 찾을 수 있다. 가장 작은 약수는 1이므로 모든 경우에 수빈이는 동생을 찾을 수 있다. 각 $dir_i$의 약수들에 대..