개발 블로그

https://www.acmicpc.net/problem/2210 2210번: 숫자판 점프 111111, 111112, 111121, 111211, 111212, 112111, 112121, 121111, 121112, 121211, 121212, 211111, 211121, 212111, 212121 이 가능한 경우들이다. www.acmicpc.net DFS + Bruteforce 문제입니다. 중복 값을 제거해주는 Set를 선언해줍니다. 그리고 길이가 6이 될 때 까지 값을 하나씩 추가해줘야하는데, 예시를 들어 값이 112에서 1을 추가한다면 112(기존 값) * 10 + 1(새로운 값)이 되어야 합니다. 그래서 함수 세 번째 파라미터에서 함수 num * 10 + a[nx][ny]를 호출해주었습니다. ..

https://www.acmicpc.net/problem/17089 17089번: 세 친구 첫째 줄에 사람의 수 N(3 ≤ N ≤ 4,000), 친구 관계의 수 M(0 ≤ M ≤ 4,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계를 의미하는 두 정수 A, B가 주어진다. 친구 관계는 A와 B, 그리고 B와 A가 친 www.acmicpc.net 이 문제는 A, B, C의 각각의 친구의 수의 최솟값을 구하는 문제입니다. 우선적으로 A, B가 친구 관계인지 check해주고, A, B가 친구인 경우에 C가 친구인 경우를 구한다면, 시간 복잡도를 O(N^3)에서 O(N^2 + MN)으로 최소화할 수 있게 됩니다. #include using namespace std; int a[4001][4001]; i..

https://www.acmicpc.net/problem/16922 16922번: 로마 숫자 만들기 2, 6, 10, 11, 15, 20, 51, 55, 60, 100을 만들 수 있다. www.acmicpc.net 비교적 간단한 브루트포스 문제였습니다. 우선적으로 I,V,X,L을 사용하여 만들 수 있는 로마 숫자의 개수를 반환해야 합니다. 그런데 for문을 4번 돌리게 된다면, 시간 복잡도가 O(n^4)이 되기 때문에 다른 방안을 생각해야 합니다. I+V+X+L = n(사용할 로마 숫자 개수)이 되어야 합니다. 그러면 가장 큰 수를 나타내는 L의 개수는 n-X-V-I가 됩니다. 나머지 부분은 가장 작은 수 I부터 n까지 탐색하고, V는 n-I까지, X는 n-I-V까지 탐색해서 만들 수 있는 로마 숫자의 ..

https://www.acmicpc.net/problem/16917 16917번: 양념 반 후라이드 반 현진 치킨에서 판매하는 치킨은 양념 치킨, 후라이드 치킨, 반반 치킨으로 총 세 종류이다. 반반 치킨은 절반은 양념 치킨, 절반은 후라이드 치킨으로 이루어져있다. 양념 치킨 한 마리의 가격은 www.acmicpc.net 문제에서 주어지는 입력 값은 양념치킨 값, 후라이드 치킨 값, 반반 치킨 값, 만들어야 할 양념치킨, 후라이드 치킨의 개수이다. 이 문제에서 신경 써야 할 부분은 반반 치킨이다. 반반 치킨을 기준으로 완전탐색(브루트 포스)을 하여 최소 금액을 구할 수 있게 됩니다. #include #include using namespace std; int main() { int a,b,c,x,y; c..