https://www.acmicpc.net/problem/74534개의 배열 A,B,C,D가 주어졌을 때 해당 배열들에서 수를 하나씩 선택했을 때 선택한 수들의 합이 0인 경우가 몇가지인지 구하는 문제다.나이브하게 4중포문으로 구현이 가능하긴 하지만 아무리 제한시간이 12초라도 4000을 네 번 곱하면(N⁴) 시간초과가 당연하다.(N = 1억에 1초로 생각하면 된다) 아이디어는 선형대수학을 떠올렸는데 선형대수학에서 ABx = C의 방정식을 풀때 행렬 AB를 구하는 과정에 O(N³)이 걸리기 때문에 Bx를 치환함으로써 O(N²) 두번으로 문제를 해결했었다. 이 문제도 4중포문 대신 AB의 모든 경우의 수를 계산하고(O(N²)), CD의 모든 경우의 수를 계산해서(O(N²)) AB배열과 CD배열을 투포인터로..

https://www.acmicpc.net/problem/2655벽돌은 회전시킬 수 없다. 즉, 옆면을 밑면으로 사용할 수 없다.밑면의 넓이가 같은 벽돌은 없으며, 또한 무게가 같은 벽돌도 없다.벽돌들의 높이는 같을 수도 있다.탑을 쌓을 때 밑면이 좁은 벽돌 위에 밑면이 넓은 벽돌은 놓을 수 없다.무게가 무거운 벽돌을 무게가 가벼운 벽돌 위에 놓을 수 없다.위의 조건을 만족하면서 가장 높게 탑을 쌓아야한다. 입력으로 주어지는 벽돌의 개수가 100개 이하이므로 모든 경우의 수를 다 훓어보기에 충분하다. 훓을때 고려해야할 조건이 무게가 높은 블럭, 밑면적이 큰 블럭이 밑에 쌓여야만 한다.본인은 밑면적 순으로 정렬해서 탐색할때 밑면적이 큰 놈이 밑으로 오게 하고 무게 조건은 if문으로 처리했다. Dp[i]가 ..

https://www.acmicpc.net/problem/31443초코바의 가로 세로 길이가 입력으로 주어지고 초코바를 쪼갰을때 나눠주는 조각의 넓이가 기쁨이고 준영이가 얻는 기쁨은 나눠준 기쁨의 총 곱이다. 이 문제는 백준1437번 수 분해와 완전히 똑같은 문제이다. 구체적인 증명이 어려운 문제인데 결론적으로는 1*3짜리를 가장 많이 만들면 된다. 어떤 자연수(원래 초코바의 넓이)를 분해한 수들(초코바 조각들의 넓이)의 곱(총 기쁨)은 3을 가장 많이 사용했을 때 가장 커진다. 자연수가 아니라면 자연상수인 e(2.718xxx...)의 제곱들이 가장 큰 수를 만든다. 문제의 조건에서 초코바 조각들의 길이는 항상 정수여야한다고 했으므로 e와 가장 가까운 3으로 나누는 경우가 가장 곱들이 커지는 경우가 된다..

https://www.acmicpc.net/problem/24025돌의 정령의 무리의 키가 4 1 5 2 3 이라면 왼쪽수터 시야 점수는 2 0 INF 0 INF 가 된다. 자신의 무리보다 키가 큰 무리 전까지의 돌의 정령 무리 수가 시야 점수가 된다. 문제에서 돌의 정령 무리수와 동일한 개수만큼의 숫자가 주어진다. 주어진 숫자가 A(A>0)일 경우 해당 숫자가 주어진 인덱스의 돌의 정령의 시야점수가 A이상이 되도록, 주어진 숫자가 -A(-A ★Point1. 마지막에 배치되는 돌의 정령의 시야점수는 항상 INF이다.2. 돌의 정령의 무리가 N~1까지 내림차순으로 배치되면, 모든 돌의 정령의 무리의 시야점수는 INF이다. 돌의 정령의 시야점수가 딱 A가 되게 만드는 것이 아니라 A이상 -A이하로 만들어도 ..

https://www.acmicpc.net/problem/75613 X 3 동차선형연립방정식을 크래머의 공식을 이용하여 풀어내라는 문제다.선형대수학에 나오는 개념이며, Determinant(행렬식)의 개념을 알고 있으면 문제를 이해하기 쉽다.크래머 공식을 단순 구현하는 문제이긴 부동소수점을 조절해주어야 하고, 선형대수학에 나오는 개념을 미리 알고 있는 사람이 아니면 생각보다 코드를 작성하기 시작하는데 오래걸릴거 같다. 각 원소의 범위가 -1000 ~ 1000이므로 행렬식을 계산하는 도중에 int형 범위를 넘어갈 수 있음에 유의하자.#include #define ep 0.0005#define lint long longusing namespace std;lint n, detA, detA1, detA2, de..

https://www.acmicpc.net/problem/31404분리집합으로 풀어야 하나 했는데 사이클을 어떻게 잡아야 할지 감이 안오고, 입력값들의 범위가 딱 봐도 구현이길래 구현만 하자라는 마인드로 풀었다.먼지를 청소했을때는 ruleA를 따르고, 아닐때는 ruleB를 따르며 움직여야 한다. 3차원 배열을 이용해서 특정 위치 (r,c)에 들어가는 방향이 같은 경우 사이클이 생기므로 반복을 종료하면 된다.또 중요한 건 먼지를 치웠을 때 사이클 확인을 위해 저장해놓은 3차원 배열을 모두 처음 상태로 초기화 시켜주어야 한다. ruleA와 ruleB가 다르기 때문에 같은 방향으로 들어가더라도 다음 이동이 달라질 수 있기 때문이다. 개인적으로 어려웠던 문제다.#include #include #include #..