백준 21818 - Do You Know Your ABCs? [완전탐색]

문제를 거꾸로 생각해보았다. (A, B, C)가 있을 때 [A, B, C, A+B, A+C, B+C, A+B+C] 를 만들었다고 치면 Elsie가 말한 숫자들이 전부 위 배열 안에 있어야 한다. 그렇다면 A, B, C가 될 수 있는 후보군이 뭘까? 우리가 찾을 수 있는 숫자들은 위에 7개밖에 없다. 위의 숫자들을 더하거나 빼면 후보군이 나올수가 있다. (A+B+C) - (A+B) = C - (A+C) = B - (B+C) = A - (A) = B+C - (B) = A+C ..... .. 이렇게 숫자를 뺀다가 핵심인거 같다. 받은 배열의 숫자의 차들이 답의 후보군이다. Elsie가 말한 배열을 L이라고 하고 (A, B, C)로 만들 수 있는 숫자들의 전체 배열을 tmp라고 해보자. 그러면 set(tmp) ..

• format_list_bulleted 백준/완전탐색
• · 2023. 7. 13.
• textsms

백준 1438 - 가장 작은 직사각형 [중복조합, 완전탐색]

문제 현수는 어떤 좌표 평면에 점을 N개 찍었다. 신기하게도, 모든 점은 음이 아닌 정수 좌표에만 찍혔다. 현수는 직사각형을 하나 그리려고 하는데, 직사각형의 꼭짓점은 모두 정수 좌표이고, 모든 변이 X축과 Y축에 평행한 직사각형을 그리려고 한다. 또, 직사각형의 내부에 현수가 찍은 점이 적어도 N/2개가 들어있는 직사각형을 그리려고 한다. 점이 직사각형의 변 위에 놓여져 있는 것은 내부에 있는 것이 아니다. 이러한 직사각형 중에 넓이가 가장 작은 직사각형의 넓이를 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 점의 개수 N이 주어진다. N은 항상 짝수이며, 100보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 현수가 찍은 점의 정보가 X좌표 Y좌표 순으로 들어온다. 각각의 좌표는 10,000보..

• format_list_bulleted 백준/기타
• · 2023. 6. 29.
• textsms

[c++] 백준 1007 - 벡터 매칭 [next_permutation]

벡터 매칭 성공 문제 평면 상에 N개의 점이 찍혀있고, 그 점을 집합 P라고 하자. 집합 P의 벡터 매칭은 벡터의 집합인데, 모든 벡터는 집합 P의 한 점에서 시작해서, 또 다른 점에서 끝나는 벡터의 집합이다. 또, P에 속하는 모든 점은 한 번씩 쓰여야 한다. 벡터 매칭에 있는 벡터의 개수는 P에 있는 점의 절반이다. 평면 상의 점이 주어졌을 때, 집합 P의 벡터 매칭에 있는 벡터의 합의 길이의 최솟값을 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 구성되어있다. 테스트 케이스의 첫째 줄에 점의 개수 N이 주어진다. N은 짝수이다. 둘째 줄부터 N개의 줄에 점의 좌표가 주어진다. N은 20보다 작거나 같은 자연수이고, 좌표는 절댓값..

• format_list_bulleted 백준/구현, 수학
• · 2022. 5. 31.
• textsms

[c++] 백준 11729 - 하노이 탑 이동 순서 [구현?재귀?]

세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다. 이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다. 아래 그림은 원판이 5개인 경우의 예시이다. 머리좀 식힐라고 간만에 실버문제를 풀었다. 하노이의 탑 진짜 너무 오랫만에 봐서 기억은 안났고 생각해내야 했다. 우선 천천히 하노이의 탑을 쌓아보았다. ㅋㅋㅋㅋ진짜 이러고 있었음 3짜리 두번정도 쌓아보니까 나온 점화식은 다음과 같다..

• format_list_bulleted 백준/구현, 수학
• · 2022. 5. 26.
• textsms

[c++] 17472 - 다리만들기2 [BFS][크루스칼 알고리즘]

https://www.acmicpc.net/problem/17472 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 다리의 최단거리를 구해보는 문제이다. 문제를 보면 우선 다리의 조건은 길이 2이상 직선으로만 가야함 이다. 문제의 전체적인 풀이는 다음과 같다. 구역을 나눠줌 구역별로의 거리를 구함 모든 구역을 연결하는 최소 길이를 찾음. 1, 2는 BFS를 사용해서 구한다. 3.은 프림알고리즘 혹은 크루스칼 알고리즘을 이용한다. 간선이 많지는 않은거같아 그냥 크루스칼을 사용했다. 단, 주의..

• format_list_bulleted 백준/DFS,BFS
• · 2022. 5. 25.
• textsms

[c++] 백준 15999 - 뒤집기 [카카오 코딩 페스티벌 18]

이왜맞? 을 한 문제였다. 현재 상태를 만들 수 있는 격자판을 만드는 문제이다. 반대로 뒤집어서 생각하면 현재 상태에서 새로 만들 수 있는 상태를 찾아내는 문제이다. 따라서 현재 상태를 바꿀 수 있는 경우를 모두 고르면 된다. 우선 위 예시를 보면 W B B B 이라는 상태인인데, w를 누르는 순간 모든 격자가 B로 통일되버리니 누를 수 없다. (다시 복구할 수 없기 때문) [0,1]의 B버튼을 눌러도 W랑 통합이 되어버리고, [1,0]도 마찬가지이다. 오직 오른쪽 아래 [1,1] B버튼만이 누를 수 있다. 즉, 양옆에 다른 색이 붙어있다면 해당 색과 통일되어 버려서 누를 수 없다. 모든 붙어있는 면이 같은색이면 누를 수 있다. 그리고 나는 문제를 풀 때 이 예시를 생각했다. W W W W W W B W..

• format_list_bulleted 백준/구현, 수학
• · 2022. 5. 24.
• textsms

백준 Solved.ac 코인샵 알쏭달쏭 스트릭 그래프 염색 컬러칩

방금 재밋는거 찾았다 스트릭 프리즈나 하나 사둘까 해서 들어갔는데 처음보는게 보였당 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 스트릭의 색상을 바꿔 준다고 한다 바로삼 짜잔~ 40개를 주는데 이미 세번 돌렸다 옆에 사용하기 버튼을 누르면 된다 원래모습은 이렇다 초록초록 사용하기 버튼을 누르면! 이런식으로 뜬다 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ..

• format_list_bulleted 백준/백준 코인아이템
• · 2022. 4. 23.
• textsms

[c++] 백준 16236-아기 상어

아기 상어 성공 문제 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다. 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다. 아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다. 따라서, 크기가 같은 물고기는 먹을 수 없지만, 그 물고기가 있는 칸은 지나갈 수 있다. 아기 상어가 어디로 이동할지 결정하는 방법은 아래와 같다. 더 이상 먹을 수 있는 물고기가 공간에 없다면 ..

• format_list_bulleted 백준/DFS,BFS
• · 2022. 2. 9.
• textsms