본문 바로가기

PS/BOJ757

백준 10542 자바 - 마피아 게임 (BOJ 10542 JAVA) 문제 : https://www.acmicpc.net/problem/10542 오랜만에 엄청 재밌는 문제였다. 그다지 복잡한 알고리즘적 지식을 요구하지 않으면서도 이렇게 난이도도 어느정도 있으면서 재밌게 낸것도 모자라서, 심지어 예제 입력들도 풀이를 생각하기 편하게 잘 내줬다. 출제자 멋져 AD-HOC 문제로, 딱 이거다! 하는 해법 없이 논리적으로 맞다고 생각하는 방식들을 찾아 적용하며 풀어야 하는 문제이다. 일단 풀이과정은 한가지 확실한 조건(이하 '1'이 이에 해당함)에서 시작하면 판정을 위한 다른 방식들로 생각을 이어갈 수 있다. 1. 문제에서 제시된 '마피아끼리는 서로 누군지 아는 상황이기 때문에 서로 지목을 안 하려고 할 것이다.'에 따라, 일단 맨 처음에 들어온 입력에서 한 번이라도 지목을 당.. 2021. 11. 18.
백준 16509 자바 - 장군 (BOJ 16509 JAVA) 문제 : https://www.acmicpc.net/problem/16509 기본 BFS 문제다(구현이 상당히 귀찮은). 좀 덜 귀찮으려면 다음과 같이 하면 된다. 1. BFS 이동 위치를 문제에서 제시된 이동 위치 끝 지점만으로 한다. (코드의 dr, dc) 2. 이동하면서 장군에 걸리는 지점의 경우 이동이 불가하므로, 이 부분에 대한 체크 중 첫번째로 '상'의 상하좌우에 위치한 부분을 체크한다. (코드의 'switch (d)' 부분) 3. 다음으로 나머지 이동구간에 있는 지점들은, '1'에서 지정한 위치에서 대각선으로 한칸 이동한 위치이다. (코드의 'if (cr+dr[d]+(dr[d] 2021. 11. 18.
백준 17394 자바 - 핑거 스냅 (BOJ 17394 JAVA) 문제 : https://www.acmicpc.net/problem/17394 일단 A와 B 사이의 소수라는 조건이 없다고 생각해보자. 이 경우 1차원 좌표평면 상에서 시작점으로 부터 1. 현재위치/2 2. 현재위치/3 3. 현재위치-1 4. 현재위치+1 으로 이동하는 BFS 문제라 볼 수 있다. 그럼 이제 A, B 사이의 소수를 도착점으로 하는 방법만 찾으면 된다. B의 최대값은 100000이므로, 100000까지의 모든 소수만 찾으면 된다. 이 때, 당연하게도 매번 소수판정을 하면 시간초과가 날 것이다. 그러니 TC들 진행하기 이전에, 100000까지의 모든 소수를 찾아두면 된다. 이 경우 에라토스테네스의 체 방식으로 구해두면 편하게 소수를 구할 수 있다. 이 때 100000의 square root 까.. 2021. 11. 17.
백준 10282 자바 - 해킹 (BOJ 10282 JAVA) 문제 : https://www.acmicpc.net/problem/10282 가중치가 있는 방향 그래프에서 한점에서 시작해, 다른 모든 정점으로의 최단거리를 찾는 문제이다. 출력해야 하는 '총 감염되는 컴퓨터 수'는 최단거리가 무한대가 아닌 경우 즉 도달할 수 있다면 감염되는 컴퓨터이다. '마지막 컴퓨터가 감염되기까지 걸리는 시간'은 모든 정점으로의 최단거리 중 최대치를 출력하면 된다. 가중치가 있으므로 일단 BFS는 사용할 수 없고, DFS로는 시간초과를 피할 수 없다. Floyd-Warshall로는 O(100*10000^3) 이므로 역시 시간내에 통과할 수 없다. 쉽게 생각할 수 있는 이 문제에 딱 맞는 알고리즘은 다익스트라(dijkstra)이다. 시간복잡도는 대략 O(ElogV) 정도로 잡는다. -.. 2021. 11. 16.
백준 20310 자바 - 타노스 (BOJ 20310 JAVA) 문제 : https://www.acmicpc.net/problem/20310 사전순으로 가장 빠른 것이 되려면 결국 최대한 0이 앞쪽으로 와야하고, 최대한 1이 뒤쪽으로 가야한다. 그래서 생각보다 간단하게 풀 수 있는데, 단순히 1은 앞에서부터 지우고, 0은 뒤에서부터 지우면 된다. 다음과 같은 경우를 보자. 1은 4개이므로 2개를 지워야 한다. 0은 2개이므로 1개를 지워야 한다. 로직은 다음과 같다. 1. 편히 풀기위해 문자열을 character 배열 형태로 변경한다. 2. '1'이 들어있는 부분만 보면서, 지워야 하는 개수만큼 앞에서부터 순서대로 지운다. (따라서 이 풀이는 그리디!) 3. '0'이 들어있는 부분만 보면서, 지워야 하는 개수만큼 뒤에서부터 순서대로지운다. --- 코드 : https:.. 2021. 11. 14.
백준 3273 자바 - 두 수의 합 (BOJ 3273 JAVA) 문제 : https://www.acmicpc.net/problem/3273 보통 풀고보면 풀이 방법이 비슷비슷한 경우가 많은데, 아무래도 입력값 n이 10만개 밖에 안되다보니 재밌게도 풀이방법이 매우 다양한 문제이다. 일단, 단순히 2중 반복문으로 모든 쌍을 더해보면 O(N^2)이므로 시간초과다. 그럼 그 외에 시간 내에 가능한 풀이법에 대해 보자. 일반적으로 사람들이 많이 사용한 풀이 방법은 2가지 정도 있었다. 1. 정렬 후, 모든 값을 확인하며 x-a_i가 존재하는지 이분탐색으로 확인 : 정렬 O(NlogN) + N개에 대한 이분탐색 O(NlogN) 2. 정렬 후, 투 포인터 알고리즘으로 맨앞과 맨뒤에서 시작한 포인터를 움직이며 더해봄 : 정렬 O(NlogN) + 탐색 O(N) --- 내 경우엔 b.. 2021. 11. 13.
백준 9421 자바 - 소수상근수 (BOJ 9421 JAVA) 문제 : https://www.acmicpc.net/problem/9421 일단 이 문제를 풀기 위해 필요한 부분을 살펴보자. 1. 1000000이하의 모든 소수를 알 수 있어야 한다. -> 소수판정의 경우 간단히 에라토스테네스의 체를 사용해서 100만 이하의 모든 수에 대해 미리 소수를 구해두면 된다. 2. 상근수를 구할 수 있어야 한다. 이 때 '1'이 아예 안나오는 경우가 존재하므로 무한루프로 빠지지 않도록 하는 로직이 필요하다. -> 1이 나오거나, 이미 나왔던 수가 다시 나올 때 까지(순환) '각 자리수의 제곱의 합'을 구해준다. 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/09400/BOJ_9421.java import.. 2021. 11. 13.
백준 2811 자바 - 상범이의 우울 (BOJ 2811 JAVA) 문제 : https://www.acmicpc.net/problem/2811 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/02800/BOJ_2811.java 정리하자면 결국 다음과 같다. 1. 연속된 음수 날의 개수(우울 기간)를 센다. 2. 해당 우울 기간 * 2 배 이전부터 꽃을 준다. 3. 그 중 가장 우울 기간이 긴 날들을 살펴보면서, 3배 이전부터 선물을 줬을 때 가장 많은 꽃을 사줘야 하는 경우를 고르면 된다. 그럼 내가 푼 로직은 다음과 같다. 1. 배열로 값들을 입력받는다. 2. 연속된 음수값에 대해 해당 음수값이 시작한 위치에 '우울 기간(T)'을 기입한다. 다음의 경우를 보자. 15 -4 2 5 -1 -3 4 -5.. 2021. 11. 12.
백준 1501 자바 - 영어 읽기 (BOJ 1501 JAVA) 문제 : https://www.acmicpc.net/problem/1501 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/01500/BOJ_1501.java 문제 자체는 해싱처리만 알면 풀 수 있는 문제인데, 설명이 너무 불명확하다 ㅡㅡ.. N개의 단어에 포함되지 않는 단어가 포함된 문장은 '0'을 출력해야한다.. 대체 문제 어디에 그 내용이 적혀있는데 ㅠ 뭐 굳이 억지로 찾아보자면 '각각의 단어들이 실제로 존재하는 단어(사전에 존재하는 단어)일 경우에만 의미가 있다.' 부분일 것 같긴하다만.. 1. 첫 문자와 끝 문자는 무조건 같아야 한다. 그 내부의 문자들은 소문자 a~z, 대문자 A~Z로 나눠서 카운팅하면 ababa, aabb.. 2021. 11. 12.
백준 2405 자바 - 세 수, 두 M (BOJ 2405 JAVA) 문제 : https://www.acmicpc.net/problem/2405 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/02400/BOJ_2405.java 1. a 2021. 11. 12.

티스토리툴바