본문 바로가기

BOJ737

백준 21941 자바 - 문자열 제거 (틀린 풀이 - 새로 작성한 풀이 링크 포함) -- 이하 틀린 풀이이다. -- 새로 작성한 풀이 : 링크 문제 : https://www.acmicpc.net/problem/21941 풀고보니 DP로만 분류되있어서(알고리즘 분류 켜놓으면 너무 치트라 꺼놨음) 약간 의아했다. 내 경우엔 그리디로 풀었다. 물론 DP를 더 간단하게 생각하는 분들이 많겠지 ㅠ 1. 일단 a의 길이가 x보다 크거나 같다면 버린다. 예제 입력2의 경우를 처리하기 위해서이다. 2. 그다음 가장 점수를 많이 주는 녀석부터 하나씩 빼낼껀데, 단순히 'x'만 판단하면 안된다. 왜냐면 다음과 같은 경우가 있을 수 있다. abcdefg 10 a 9 둘 다 '1'에서 걸러지지 않지만, 누가봐도 'a 9'를 쓰는게 이득임을 알 수 있다. 따라서 [ x / a의길이 ] 가 높은 순서대로 먼저 .. 2021. 10. 23.
백준 1294 자바 - 문자열 장식 (BOJ 1294 JAVA) 문제 : https://www.acmicpc.net/problem/1294 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/01200/BOJ_1294.java 쉬운줄 알고 덤볐는데 생각보다 어려웠지만, 결국 다 풀고보니 또 그렇게 어렵진 않았던 문제. 1. 기본 로직은 어렵지 않게 생각해볼 수 있다. 3 ABC BCD CDE 만약 입력이 위와 같다고 하자. 각 문자열의 순서를 해치지 않으면서 전체 문자열이 사전순으로 앞서게 하려면 결국 각 문자열에 pointer를 뒀다고 생각하고, 해당 문자열의 pointer가 가르키는 문자 중 가장 작은걸 순서대로 빼내면 된다. 즉, 위의 경우 다음과 같이 진행된다. 1.1 시작은 아래와 같다. 화.. 2021. 10. 23.
백준 23276 자바 - Locust Locus (BOJ 23276 JAVA) 문제 : https://www.acmicpc.net/problem/23276 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/23200/BOJ_23276.java 결국 k개의 입력 중 y + (c1과 c2의 최소공배수) 의 최소값을 찾으면 된다. 최소공배수는 유클리드 호제법을 통해 구했다. 2021. 10. 22.
백준 2660 자바 - 회장뽑기 (BOJ 2660 JAVA) 문제 : https://www.acmicpc.net/problem/2660 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/02600/BOJ_2660.java 사실상 언어영역 문제였다. '예를 들어 어느 회원이 다른 모든 회원과 친구이면, 이 회원의 점수는 1점이다. 어느 회원의 점수가 2점이면, 다른 모든 회원이 친구이거나 친구의 친구임을 말한다. 또한 어느 회원의 점수가 3점이면, 다른 모든 회원이 친구이거나, 친구의 친구이거나, 친구의 친구의 친구임을 말한다.' 대체 이게 뭔 X소리인가 해서 일단 공책에 그래프 그려보고 서로 몇다리 건너뛰어야 하는지 그려보고 생각해보기로 했다. 결론적으로 문제에 제시된 예제1은 다음과 같이 그려.. 2021. 10. 22.
백준 23256 자바 - 성인 게임 (BOJ 23256 JAVA) 문제 : https://www.acmicpc.net/problem/23256 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/23200/BOJ_23256.java 규칙성을 찾기가 난해했다. 일단 결과부터 말하자면 이 문제는 점화식 2개를 만들어 풀어야 한다. 전체 경우의 수를 따로 세고, 전체의 경우 중 맨 우측이 1칸짜리 블록인 경우를 따로 세야 한다. 예를들어 N=1인 경우 전체 경우의 수는 7이고, 맨 우측이 1칸짜리 블록인 경우 3가지로 다음과 같다. 그럼 왜 그렇게 해야하는지 풀이를 써보겠다. 1. N=2 이상일 경우 이전 경우에서 우측에 3개가 추가된다. 이 때 그 3개는 다음의 3가지 경우가 있다. 따라서 일단 f(n)이.. 2021. 10. 21.
백준 1270 자바 - 전쟁 - 땅따먹기 (BOJ 1270 JAVA) 문제 : https://www.acmicpc.net/problem/1270 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/01200/BOJ_1270.java 실3지만, 자바로는 메모리초과 때문에 개인적으로 골드 상위정도는 될 듯 하다. 일단 자바로 성공한게 현재로썬 혼자뿐이다. 문제 자체는 그냥 카운팅만 잘 하면 되는 쉬운 문제이므로 해설은 이 문제를 자바로 도전할 사람들을 위해 메모리를 감소시킨 방식과 일부 이해하기 힘들 수 있는 코드 부분에 대해 적어본다. 1. 일단 입력 최대치가 2^31-1이 아니고 int형 범위를 1 넘어간 2^31 이라는 점에서 악의성이 다분하다. 그냥 대충 해싱으로 t개 전부 카운트 하려 했더니 메모리 .. 2021. 10. 21.
[자바] 프로그래머스 - 3 x n 타일링 [코딩테스트 연습 Lv4] - 문제 출처 : 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges - 지형이동 문제 : https://programmers.co.kr/learn/courses/30/lessons/12902 - 코드 : 깃헙 일반적으로 DP 기본 문제로 풀어봤을 2 x n 타일링과 크게 다르지 않다. 2 x n 타일링에서 규칙성이 좀 더 찾기 어려워졌을 뿐 마찬가지로 꼼꼼하게 규칙성만 잘 찾으면 된다. 1. 우선, 2칸짜리 타일을 사용해야 하므로 무슨짓을 하던 n이 홀수라면 전체 칸 수(3 x n)가 홀수이므로 2칸짜리 타일로 타일링이 불가능하다. 즉, n이 짝수일 때만 타일링이 가능하다. 이 부분은 예외로 처리해준다. (코드 10line) 2. 가장 기본적인 .. 2021. 10. 21.
백준 16497 자바 - 대출 요청 (BOJ 16497 JAVA) 문제 : https://www.acmicpc.net/problem/16497 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/16400/BOJ_16497.java 이 문제의 경우, 31일까지 모든 날짜에 대해 현재 대출되어 있는 책의 수를 세보면 간단히 풀 수 있다. 이 때 주의점은 (3, 6)이라면 3일에 빌려서 6일 0시에 딱 반납된다고 생각하면 된다. 즉, (3, 6)과 (6, 8)이 있다면 k=1 일때도 처리할 수 있다는 의미이다. 따라서 (3, 6)이라면 3일에 빌려서 5일까지만 가지고 있다고 생각하면 된다. 그럼 문제에 나온 기본 예시 (1, 2), (3, 6), (5, 8)은 다음과 같이 나타낼 수 있다. 이와 같이 모든.. 2021. 10. 19.
백준 16666 자바 - Guest Student (BOJ 16666 JAVA) 문제 : https://www.acmicpc.net/problem/16666 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/16600/BOJ_16666.java 어렵진 않고 그냥 수학적으로 생각해서 구현하면 되는거긴한데.. 코드보면 알겠지만 이래놓고 실버라니 숭악하다. 0. 일단 매 TC 마다 입력을 받아두고(14line), 1로 시작하는 위치에서 모두 시작해본다. (15~16line) 1. 거기서 부터 일단 k가 0이될 때 까지 돌려본다.(19~22line) -> 이 때 k가 0이 된다면 그걸로 해당 회차는 끝 (23line) -> 그렇지 않다면 다음 로직으로 2. 다음으로 중간 부분은 수학적으로 나눗셈을 활용해서 날려버릴 수 있.. 2021. 10. 18.
백준 11376 자바 - 열혈강호 2 (BOJ 11376 JAVA) 문제 : https://www.acmicpc.net/problem/11376 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/11300/BOJ_11376.java 기본적인 형태의 이분 매칭 문제이다. 다만 한 사람당 2개의 일을 할 수 있으므로, n을 2배로 늘렸다. 이 때 간선 정보는 n개만 유지할 수 있도록 하는것이 좋다. 내 경우엔 그래서 간선정보를 n개 받아두고, e[n/2] (12line) 형태로 받아온다. 사실 이분 매칭에서 매칭시킬 때, 기본형태에서 그 안에 들어있는 n의 번호 자체는 중요한게 아니므로(같던 다르던 상관 없음) 코드의 45line처럼 for문 돌릴 필요 없이, 그냥 그 내에서 다시한번 2번을 돌리도록 해도.. 2021. 10. 17.

티스토리툴바