본문 바로가기

BOJ737

백준 2786 자바 - 상근이의 레스토랑 (BOJ 2786 JAVA) [ 백준 2786 - 상근이의 레스토랑 ] [ 코드 보기 (깃헙 링크) ] 쉬운 것 같으면서도 은근 생각할게 좀 있었다. 일단 생각 과정을 적어본다. 1. 첫 음식이 A가격이 아니고 B가격만 있었다면 어떻게 계산할까? -> 음식을 입력받은 순서와 관계없이 B가격만 영향을 끼치므로, 그리디하게 B 가격 순서대로 구매한다고 생각하면 된다. 따라서 B를 기준으로 정렬한 후 prefix sum(누적 합) 배열 하나 만들어두면 쉽게 출력 가능하다. 결국 첫 음식은 A가격을 지불해야 하는 부분만 잘 처리하면 되는 문제이다. 2. 음식을 1개 시킬 때 최소 가격 : [전체 중 최소 A 값] 3. 음식을 n개(전부) 시킬 때 최소 가격 : [모든 B를 더한 값] + [(A-B)의 최소값] -> 2,3번을 합쳐서 그럼 .. 2021. 11. 6.
백준 17469 자바 - 트리의 색깔과 쿼리 (BOJ 17469 JAVA) [ 백준 17469 ] [ 코드 (깃헙) ] 트리의 부모를 알려주고, 주어진 쿼리를 해결해야 한다. 쿼리는 '1 a'와 같이 들어오면 간선 제거, '2 a'와 같이 들어오면 a에서 갈 수 있는 정점들에 포함된 색깔 종류의 개수를 출력해야 한다. 당연히 매번 쿼리를 진행하고 bfs나 dfs로 갈 수 있는 경로를 찾고 또 해당 노드들에 존재하는 색깔 종류를 셀 순 없다(시간초과). 그럼 일단 각 부분들을 뭘 이용해 구할 수 있을지 확인해보자. 1. 갈 수 있는 정점들 확인 : union-find를 사용한 그룹짓기 2. 각 그룹에 포함된 색깔 종류의 개수 : HashSet을 사용하면 애초에 동일한 색깔이 중복해서 안들어가니, 해당 set의 size()만 확인하면 해당 그룹에 포함된 색깔 종류의 개수를 알 수 .. 2021. 11. 4.
백준 13306 자바 - 트리 (BOJ 13306 JAVA) [ 백준 13306 ] [ 코드 (깃헙) ] 트리의 부모를 알려주고, 주어진 쿼리를 해결하는 문제이다. 쿼리는 '0 b'와 같이 들어오면 b번째 edge 제거하는 쿼리와, '1 c d'와 같이 들어오면 c와 d 사이에 연결경로가 있는지 묻는 쿼리가 있다. 일단 거리 자체를 묻지 않고, 연결 경로가 있는지만 파악하면 된다. 그럼 이거엔 union-find 알고리즘을 쓰면 될 것임을 알 수 있다. 다만 해당 알고리즘의 경우 그룹간의 관계를 맺는것은 쉽지만, 연결을 끊는건 힘들다. 그럼 쿼리를 반대순서로 보면 어떻게 될까? 원래 순서대로라면 '간선들이 존재하는 그래프에서 edge를 제거하면서 중간중간 특정 노드간에 연결경로가 있는지 묻는 쿼리' 이지만, 반대로 미리 쿼리상에 존재하는 모든 간선을 제거한 후 역.. 2021. 11. 4.
백준 1138 자바 - 한 줄로 서기 (BOJ 1138 JAVA) [ 문제보기 ] [ 코드보기(깃헙) ] N이 최대 10이다. 따라서 모든 경우를 보려면 10! 번을 봐야한다. 이 경우 362880번으로, 사실 모든 경우를 봐도 가능하긴 하다! 다해봐야 O(N! * N) 정도이다. 사실 시간복잡도, 메모리복잡도 면에서 모두 이득인 방법이 더 있다. 어차피 입력이 키가 1인 사람부터 차례대로 들어오기 때문에, 키가 큰 사람부터 순서대로 입력을 만족하는 위치에 넣어버리면 된다. (따라서 그리디 알고리즘 분류다.) 4 2 1 1 0 의 입력을 확인해보자. 이 경우 키가 1인 사람은 좌측에 2명, 2인 사람은 좌측에 1명, 3인 사람은 좌측에 1명, 4인 사람은 좌측에 아무도 없다는 입력이다. 키가 작은 사람부터 보자면 어려운 문제가 확실하지만, 키가 큰 사람부터 보면 엄청 .. 2021. 11. 3.
백준 1485 자바 - 정사각형 (BOJ 1485 JAVA) [ 문제 보기 ] [ 코드 보기(깃헙) ] [ 틀린 경우 ] 처음엔 아래와 같이 축에 평핸한 정사각형을 찾는줄 알았다. 그래서 예를들어 입력이 1 1 1 1 2 2 1 2 2 와 같다면, 사실 좌측이 x축인지 우측이 x축인지는 안알려줬지만 상관없이 좌측이 2종류고, 우측이 2종류이며 각각 2번씩 나왔고, 좌측의 2종류의 차이와 우측의 2종류의 차이가 동일하다면 정사각형으로 판단하도록 했다. 이 코드는 틀렸다. [ 해설 ] 그렇다면 아래와 같이 정사각형이 기울어 있는 경우까지 찾을 수 있어야 한다. 1. 그래도 딱히 어려울건 없는데, 그냥 4개의 점을 입력받고 나올 수 있는 모든 경우의 길이를 구해본다. 4개에서 2개를 순서없이 골라야하니, 4C2 = 4P2 / 2! = 4*3/2 = 6가지만 구해보면 된.. 2021. 11. 3.
백준 1195 자바 - 킥다운 (BOJ 1195 JAVA) 문제 : https://www.acmicpc.net/problem/1195 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/01100/BOJ_1195.java 순전히 구현력에 따라 풀 수 있고 없고가 갈리는 문제이다. 길이가 최대 100이므로 그냥 brute force로 모든 경우를 시뮬레이션 돌려도 전혀 문제가 없다. 1. 일단 최대로 나올 수 있는 경우는 예를들어 모든 부분이 '이'로 되어 있다면 서로 겹칠 수 없으니 두 문자열의 합이 일단 최대치이다. 그 후에, 이런 모양부터 시작해서 하나하나 직접 비교해보는 것이다. 이 때 '이'와 '이'가 만나는 경우는 맞물릴 수 없는 경우이므로 무시한다. ... --(A)-- ... 이런식.. 2021. 11. 2.
백준 1111 자바 - IQ Test (BOJ 1111 JAVA) 문제 : https://www.acmicpc.net/problem/1111 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/01100/BOJ_1111.java 쉽게봤더니 생각보다 예외처리할게 많았다. 그래도 이정도면 무난한 편인듯. 'A'와 'B'가 언제 발생할지만 잘 생각해보면 된다. 1. 우선 n이 2 이상일 때 첫번째 수와 두번째 수가 동일한 경우를 생각해봐야 한다. 이게 찾기 제일 어려웠다. [1 1 1 1 ...] 이런 경우이다. 처음엔 2차방정식이 안풀리니 당연히 'A'일꺼라 생각했는데, 2x-1 과 같은 경우 가능하다. 그러니 동일한게 이어진다면 동일한 값을 출력만 해주면 된다. 다만 [1 1 2 ..] 이렇게 갑자기 숫.. 2021. 11. 2.
백준 23334 자바 - Olympic Ranking (BOJ 23334 JAVA) 문제 : https://www.acmicpc.net/problem/23334 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/23300/BOJ_23334.java 브론즈 티어지만 자바 한정으로 시간초과 날 위험이 큰 문제라 남겨봅니다. 자바에 시간 어드밴티지 없이 모든 언어 동일하게 1초 제한인 문제입니다. 이 문제의 경우 일반적으로 생각할 수 있는, 입력받은걸 배열에 넣고 정렬하는 방식으로 하게 되면 시간초과가 날 확률이 있습니다. g,s,b가 최대 999이고, g,s,b 순서대로 비교가 되면 되므로 g*1000000 + s*1000 + b 로 처리를 하게되면 최대 10억-1 이므로 int형으로 한방에 표현 가능합니다. 예를들어 g.. 2021. 11. 2.
백준 22728 자바 - Amida, the City of Miracle (BOJ 22728 JAVA) 문제 : https://www.acmicpc.net/problem/22728 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/22700/BOJ_22728.java 일본어로 된 문제라 번역기 돌려야 한다는 점을 빼면 그냥 문제에 제시된 대로 구현만 하면 된다. 내 경우엔 arr[a][b] = c를 a높이에서 b번 수직선에서 c번 수직선으로 넘어갈 수 있다로 정의했다. 따라서 h, p, q를 입력받을 시 arr[h][p] = q, arr[h][q] = p가 된다. 그리고 높이 1001(가로선이 높이 1000부터 있을 수 있으므로)부터 높이를 1씩 감소시키면서 해당 높이에서 이동할 가로선이 있으면 무조건 이동하는 방식으로 짰다. 최종적으로.. 2021. 10. 30.
백준 1004 자바 - 어린 왕자 (BOJ 1004 JAVA) 문제 : https://www.acmicpc.net/problem/1004 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/01000/BOJ_1004.java 사실 문제에 있는 복잡한 그림을 보고 쫄지만 않으면 된다. 그냥 시작지점과 끝지점이 각 원에 포함되는지만 확인하면 된다. 1. 둘다 포함하거나, 둘다 포함안되면 지나갈 필요가 없다. 2. 둘 중 하나만 포함되면 지나가야 한다. 원의 x,y 좌표와 시작점, 끝점의 좌표에 대해 각각 거리를 구해 반지름보다 작다면 포함되니 그걸로 판단하면 된다. 2021. 10. 29.

티스토리툴바