반응형 컴퓨터 사이언스/BOJ42 [c++] 백준 #3830 교수님은 기다리지 않는다. 맨처음엔 정말 naive하게 O(N^2) dfs 풀이로 진행했다가 TLE를 맛보고 union disjoint set을 이용해서 풀어야 한다는 것을 알게 되었다. b가 a보다 무겁다는 걸 그래프로 나타내면 아래와 같다. b가 무거우니까 diff[b] - k = diff[a]가 된다. 여기서 b와 a에게 부모가 있다는 걸 생각하고 그래프를 그려보자. b의 부모에 a의 부모를 붙일거면 diff[b] - k = x + diff[a]가 성립한다. 따라서 x = diff[b] - diff[a] - k가 된다. 반대로 a의 부모에 b의 부모를 붙일 거면 -x를 붙여주면 된다. ** 각 테케마다 p, diff, n을 초기화해줘야하는데 여기서 실수로 for문 2개를 넣어버려서 이상한 곳에서 TLE가 나서 나.. 2019. 10. 14. [c++] 백준 #6531 이런 문제는 유치원생도 해결할 수 있어 분할정복 문제이다. 이때 중복해서 계산하는 게 있어서 시간초과를 피하기 위해서는 dp배열을 써주자. 코드나 로직 자체는 최적화가 덜된 것 같지만.. 로직을 간단하게 설명하면, {}으로 되어 있으면 set이고, {}안에 있는 것들이 ","를 기준으로 elem인지 확인을 해주면 된다. #include using namespace std; #define INF 987654321 typedef long long ll; typedef pair ii; typedef tuple iii; #define pb push_back #define N_MAX 100010 string str; int isElem(int a, int b); int isSet(int a, int b); vector dp.. 2019. 10. 13. [c++] 백준 #1194 달이 차오른다, 가자. 너무 복잡하게 생각했는데, 그냥 BFS를 하는데 key를 가지고 있는 조건들을 비트마스킹하면 된다. key를 획득한 정보나 움직인 횟수를 count하는 변수를 잘 관리해야 꼬이지 않는다..ㅠㅠ for문 체크할 때마다 초기화해줘야 하는데 잘못하면 중복해서 count되는 경우도 있고 그렇다. 공간 복잡도는 A~F의 key만 가지고 있는 지 확인하면 되고, 전체 map이 50x50이니까 총 O(50*50*2^6)의 복잡도를 가진다. #include using namespace std; #define INF 987654321 typedef long long ll; typedef pair ii; typedef tuple iii; #define pb push_back vector mir.. 2019. 10. 13. [c++] 백준 #2879 코딩은 예쁘게 original 값과 바뀌어야 하는 값의 차이를 계산했을 때 부호가 같은 값들끼리 따로 그룹으로 묶은 후 각 그룹에서 값을 업데이트한다. 이때 조심해야하는 것은 업데이트 횟수는 각 그룹 안에서 차이 값이 가장 큰 값이라고 착각하기 쉽다는 것이다. input이 5 1 2 3 4 5 0 0 0 0 0 이런 식으로 되어 있으면 1업데이트, 1~5 업데이트, 2~5업데이트, 3~5업데이트, 4~5업데이트, 5업데이트 이렇게 5번이니까 max 취하면 되는 거 아닌가?? 할건데, 만약 input이 5 3 2 1 2 3 0 0 0 0 0 이런 식으로 되어 있으면 1~5을 업데이트 하고 나면 2 1 0 1 2 0 0 0 0 0 이런 식이 되어버린다. 그러면 이제 1~2번에서 1을 업데이트, 나머지 1에서 .. 2019. 10. 11. 이전 1 2 3 4 5 6 ··· 11 다음 반응형