문제를 해석하면 직속 상사에게 혼나면 아래도 다 혼난다그 때 모두가 혼난 정도를 출력하면 된다 트리로 구성되기 때문에 혼나는 정도를 미리 저장해두고dfs를 돌리며 자식들에게 값을 물려주면 된다 처음에 순서대로 방문한다고 혼자 착각해서 한번 틀렸다 ㅎㅎ.. 소스코드1234567891011121314151617181920212223242526272829303132333435#include #include #include using namespace std;const int MAXN = 1e5 + 5;int n, m;vector Graph;int cost[MAXN];bool check[MAXN];int ans[MAXN];void dfs(int x,int sum) { check[x] = true; int c =..
[백준] 15782 Calculate! 2
IUPC 기출 문제다세그먼트트리 + lazy를 쓰는문제 한가지 걸리는게 있다면 트리를 세그먼트트리로 바꿔야 한다는 것..!말로만 들었지 해본적이 없어서 찾아서 공부하며 풀어봤다 후위순회를 돌리고 (내위치-자식수) ~ 내위치 로 구간을 정해주면 된다!그럼 자식들 모두 업데이트를 시켜줄 수 있다 그것만 한다면 기본적인 lazy문제로 바뀐다! 소스코드123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990#include #include #include #inclu..
R495(Div.2) C. Sonya and Robots
문제를 요약하자면예를 들어 배열 [1,5,4,1,3]이 있을 때 우리는 a가 먼저 나오고 b가 나중에 나오는 순서쌍 (a,b)에 수를 찾으면 된다무슨 말이냐면 순서쌍 (1,3)은 1이 앞에 3이 뒤에 이므로 가능하다근데 (3,1) 같은 경우는 3보다 1이 앞에 있으므로 교차하게 되어 불가능하다즉 맨 앞과 맨 뒤에서 출발했을 때 교차하지 않는 순서쌍의 수를 찾으면 된다!+ 중복불가 문제는 set과 map을 사용해 풀었다map에는 각 숫자의 수를 저장했고 set은 내가 갈 수 있는 수를 의미한다그럼 맨 앞부터 수를 보면서 set의 size만큼을 더해주면 된다이 때 내가 볼 때마다 map에서 수를 1씩 줄여준다 그리고 0이 되면 set에서 사라지게 해준다추가로 used배열을 사용했는데 used는 이미 본 숫자..
[백준] 11963 High Card Low Card (Gold)
Bessis와 Elsie가 카드게임을 한다카드는 1~N*2까지 있고 그 중 입력으로 주어지는 N개를 Elsie가 가지고 있다게임의 규칙은 이렇다 Elsie는 입력 순으로 카드를 낸다처음 N/2판 까지는 카드 숫자가 큰 사람이 이긴다나머지는 숫자가 작은 사람이 이긴다 카드를 반반 쪼개서 upper_bound를 하면 답을 찾을 수 있다!처음에는 엘씨의 앞쪽카드 N/2개와 베씨의 뒤쪽카드 N/2그 다음에는 반대로 하면 된다 소스코드1234567891011121314151617181920212223242526272829303132333435363738#include #include #include #include using namespace std;int n;bool used[100005];int main() ..
[백준] 15686 치킨 배달
삼성 SW 역량테스트에 나온 문제다비트를 통해 완전탐색을 하면 답을 구할 수 있다치킨집과 집을 미리 vt에 따로 담아두고 for문을 돌리며 bit가 m개 체크된다면 지금 체크된 치킨집과 집들과의 최소거리를 다 구해보면 된다! 소스코드12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849#include #include #include #include using namespace std;int map[55][55], n, m,ccnt;vector chi, home; int dist(int x1, int y1, int x2, int y2) { return abs(x1 - x2) + abs(y1 - y2);..
[백준] 6603 로또
백트래킹으로 완탐을 이용하는 기본문제!6개의 숫자가 다 모이면 출력해주자~! 소스코드1234567891011121314151617181920212223#include #include using namespace std;int arr[50],k,n;void go(vector& vt,int pos) { if (vt.size() == 6) { for (int i = 0; i n) return; vt.push_back(arr[pos]); go(vt, pos + 1); vt.pop_back(); go(vt, pos + 1);}int main() { while (scanf(" %d", &n)) { if (n == 0) return 0; for (int i = 1; i
[백준] 13701 중복 제거
BIT를 이용해 풀 수 있는 문제다 int 형은 4byte = 32bit 이므로 1bit에 숫자 하나를 표현한다고 치면 32개의 숫자를 표현 가능하다 32 = 2^5 이고 숫자가 2^25 까지 들어오므로 2^20개의 int형이 있으면모든 숫자를 표현 가능하다 그럼 이제 int로 32개의 숫자를 표현하는 방법에 대해 알아보자이건 2차 배열에서 x,y를 숫자 하나로 표현하는 방식과 비슷하다숫자 n을 표현할 때 n/32는 몇번째 숫자로 표현 하는지 의미하고n%32 는 그 숫자에서 몇번째 비트로 표현 하는지 의미한다만약 5라면 0번째 숫자 5번째 비트이므로a[0]의 5번째 비트다 있는지 확인하려면 a[0] &( 1
[백준] 9328 열쇠
어려웠던 문제다대문자 A ~ Z는 문 // 소문자 a~z는 열쇠를 나타낸다문을 열려면 열쇠가 필요하다 이 문제에서는 홈칠 수 있는 문서의 최대 개수를 구해야 한다bfs를 돌리는데 문의 bfs를 따로 만들어 준다그래서 내가 돌아 다니다가 열수 없는 문을 만난다면 문 bfs에 따로 넣어두고 그 문을 열어주는 열쇠를 만나면 문의 좌표를 다 내가 갈 수 있게 큐에 넣어준다! 헷갈리지만 풀면 이해가 간다 소스코드12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970#include #include #include #include #inc..
[백준] 5427 불
상근이가 빌딩에서 탈출하는 가장 빠른 시간을 구해야 한다시물레이션으로 생각해서 bfs를 돌려봤다 불부터 먼저 이동하고 그다음에 상근이가 이동한다상근이의 이동 거리를 구해두고 만약 상근이가 탈출지점 까지 올 수 있다면 거리를 출력한다! 코드가 더럽다 ㅎㅎ 억지로 짠 느낌이 든다 소스코드123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100#include #include #include #include #include us..