https://www.acmicpc.net/problem/15661 15661번: 링크와 스타트 첫째 줄에 N(4 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100 www.acmicpc.net 1. Logic 팀을 꾸릴때 인원이 최대 20명이고 1명부터 팀을 꾸릴 수 있기 때문에 시간복잡도가 19!이 나온다. 이렇게 되면 시간복잡도를 한참 뛰어넘기 때문에 로직을 생각해 봐야 한다. 우리는 두 팀의 능력치의 절댓값을 판단해야 하기 때문에 1, 2, 3, 4의 인원으로 팀을 꾸리면 1,2 를 골라서 팀을 꾸리는 것과 3, 4를 골라서 팀을 꾸려서..
Algorithm/Beakjoon
https://www.acmicpc.net/problem/2442 2442번: 별 찍기 - 5 첫째 줄에는 별 1개, 둘째 줄에는 별 3개, ..., N번째 줄에는 별 2×N-1개를 찍는 문제 별은 가운데를 기준으로 대칭이어야 한다. www.acmicpc.net 1. Logic 컴공과 1학년 C언어 과목 필수 과제이다ㅋㅋㅋㅋ n=5일때를 기준으로 보면 1번째 줄 : 공백 4 / 별 1 2번째 줄 : 공백 3 / 별 3 3번째 줄 : 공백 2 / 별 5 4번째 줄 : 공백 1 / 별 7 5번째 줄 : 공백 0 / 별 9 일반화 시켜보면 0부터 시작하는 i번째 줄을 기준으로 공백의 갯수는 n-i-1 별의 갯수는 1+i*2개이다. 이대로 for문을 작성하면 된다. 2. Code #include using na..
https://www.acmicpc.net/problem/1503 1503번: 세 수 고르기 첫째 줄에 N(1 ≤ N ≤ 1,000)과 집합 S의 크기 M(0 ≤ M ≤ 50)이 주어진다. 둘째 줄에는 집합 S에 들어있는 수가 주어진다. 집합에 들어있는 수는 1,000보다 작거나 같은 자연수이고, 공백으로 구분되어 www.acmicpc.net 1. Logic 일단 입력받은 집합에 있는 숫자를 제외해야하기 때문에 bool배열을 활용하여 제외해야 하는 숫자들을 걸러줬다. 그리고 N의 범위가 1000까지이기 때문에 브루트포싱을 돌려서 1~1001까지 3중 for문을 활용하여 풀이해줬다. 시간복잡도가 1000^3 만큼 나와서 안될 줄 알았는데 내부 테케가 부족했는지 통과됐다. 이게 왜돼? 2초에 2억번 연산이라..
https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 1. Logic 기본 BFS 문제이다. 최소 이동을 고르기 때문에 우선순위 큐를 활용해서 버튼을 누르는 횟수가 가장 작은것들을 먼저 빼줬고, if문으로 조건을 나눌 때 계속 OutOfBounds가 나와서 잠깐 막혔는데, if문에서 거를 때 조건 두개가 and연산으로 묶여있으면 앞에 조건을 먼저 탐색하기 때문에if문 조건 순서를 바꿔서 해결해줬다 if(cur-d >= 1 && !vis[cur-d]) 이 부분에서..
https://www.acmicpc.net/problem/1606 1606번: 침투 계획 세우기 첫째 줄에 멍멍이의 금고의 위치를 나타내는 좌표가 주어진다. 각 수는 0이상 1,000,000이하의 정수이다. www.acmicpc.net 1. Logic x가 0이고 y>0인경우 6*i씩 증가하는 등차수열의 규칙을 가지는 것을 확인할 수 있다. 그리고 모든 입력은 양수로 주어지는 부분에 초점을 맞추면, 1을 제외한 껍질 만큼(x+y) 6을 곱해서 더해주고 만약 y가 0이면 껍질이 하나 생기는 것이기 떄문에 1을 더해준다 2. Code #include using namespace std; int main() { int x, y; cin >> x >> y; long long ans = 1; for(int i =..
https://www.acmicpc.net/problem/17386 17386번: 선분 교차 1 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. 세 점이 일직선 위에 있는 경우는 없다. www.acmicpc.net 1. Logic CCW알고리즘을 활용하여 풀이 가능하다. CCW 알고리즘이란 임의의 선분을 기준으로 다른 한 점이 시계방향으로 위치하는지 반시계방향에 위치하는지 판별할 수 있는 알고리즘이다. 이 알고리즘은 수학시간에 했던 신발끈 공식, 외적을 생각하면 쉽게 이해할 수 있다. 한 선분(선분을 이루는 두 점 A, B)과 다른 한 점(C)을 외적한 값을 CCW(A, B, C)=outer라고 했을 때 outer > 0 : ..
https://www.acmicpc.net/problem/16946 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net 1. Logic 여러가지 방법으로 시도해봤다. 시도한 방법은 1. DFS : DFS로 벽인 부분에서 이동할 수 있는 공간의 크기를 세서 저장했다. 100만개 탐색을 100만번 하니 당연히 터질 수 밖에. 그래서 DP로 접근했다. 2. DP : 한 정점에서 다른 정점으로 가는 방법을 DP로 하면 방향이 일정하기 때문에 값이 구해지지만 이번 문제는 상하좌우를 판단해야 하기 때문에..
https://www.acmicpc.net/problem/2236 2236번: 칩 만들기 당신은 칩을 만들기 위해 기판에 N개의 부품을 장착했다. 각각의 부품을 작동시키기 위해서는 전원을 연결해야 하는데, 기판에 연결할 수 있는 전원 선이 K개 밖에 없었다. 당신은 이 K개의 전원 www.acmicpc.net 1. Logic 선을 하나의 칩에 연결하면 제곱, 두개의 칩에 연결하면 연결한 두 칩의 중요도를 제곱한다. 어떤 경우든 항상 제곱하는게 이득이기 때문에 그냥 정렬해서 큰거만 k개만큼 뽑아주면 된다 풀면서도 이게 맞나 싶었다ㅋㅋㅋㅋㅋㅋ 2. Code #include using namespace std; int n, k; vector input; queue q; int trace[51]; int mai..
https://www.acmicpc.net/problem/1996 1996번: 지뢰 찾기 첫째 줄에 N(1 ≤ N ≤ 1,000)이 주어진다. 다음 N개의 줄에는 지뢰 찾기 map에 대한 정보가 주어지는데 '.' 또는 숫자로 이루어진 문자열이 들어온다. '.'는 지뢰가 없는 것이고 숫자는 지뢰가 있는 경 www.acmicpc.net 1. Logic 단순 파싱 그래프 구현 문제였다. 어렵진 않지만 c++로 파싱하려니 귀찮았다. 2. Code #include using namespace std; int n; int mine[1001][1001]; int sum[1001][1001]; char ans[1001][1001]; int dx[8] = {-1, -1, 0, 1, 1, 1, 0, -1}; int dy[..
https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net 1. Logic dp배열의 의미 : 해당 좌표를 통해 먹을 수 있는 대나무의 최대 갯수 2. Code #include using namespace std; int dx[4] = {-1, 0, 1, 0}; int dy[4] = {0, -1, 0, 1}; int n; int bamboo[501][501]; bool vis[501][501]; int dp[501][501]; int dfs(i..
