본문 바로가기

BOJ749

백준 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.
백준 2437 자바 - 저울 (BOJ 2437 JAVA) 문제 : https://www.acmicpc.net/problem/2437 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/02400/BOJ_2437.java 일단 brute force(완전탐색)으로는 단순히 생각해봐도 2^1000 이므로 절대 무리다. 처음엔 DP류 일 것 같았는데, 결론적으로 완전 아이디어 하나로 풀리는 문제였다. 내 경우엔 공책에 막 여러 케이스 무지성으로 써보면서 확인해보다가 얻어걸렸다. 일단 '양의 정수 무게 중 최솟값' 이라는 부분에서, 최소값을 찾자마자 출력해야 할꺼라 판단하여 정렬부터 하고 생각했다. 그리고 잘 보면 애초에 '2 3 4 5 6' 이렇게 있어도 1이 없으면 1은 못만든다. 그다음으로 '1 .. 2021. 11. 12.
백준 1010 자바 - 다리 놓기 (BOJ 1010 JAVA) 문제 : https://www.acmicpc.net/problem/1010 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/01000/BOJ_1010.java N=2, M=3인 경우를 보자. 이런식으로 가능하다. 그럼 좌측은 생각하지 말고, 우측 중 선택된 녀석들만 확인해보자. 위와 같다. 즉 선은 생각하지 말고, 어차피 M개 중 N개만 선택하면 되는 문제이다. 이 때 다리가 서로 겹칠 수 있다고 한다면 nPm 이겠지만, 서로 겹칠 수 없다고 했으므로 nCm이 된다. 왜냐하면 겹칠 수 있다면 다음과 같이도 놓을 수 있기 때문이다. nCm = nPm / n! 을 구하면 된다. 예를들어 N = 3, M = 5 라면 nCm = 5*4*3 .. 2021. 11. 11.
백준 5637 자바 - 가장 긴 단어 (BOJ 5637 JAVA) 문제 : https://www.acmicpc.net/problem/5637 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/05600/BOJ_5637.java 생각상으로는 그냥 공백이나 줄바꿈('\n')을 기준으로 나누면 될 것 같지만, '단어는 알파벳(a-z, A-Z)과 하이픈(-)으로만' 라는 기준에 따라 '마침표, 숫자, 심볼, 등등등...' 이라고 써져있는 것도 단어로 취급하면 안된다! 즉, '15-16 November 2012.' 라는 문장의 경우 여기서 단어는 '-', 'November'의 두가지 뿐이다. 따라서 단순히 자바의 StringTokenizer나 split으로 공백을 기준으로 나눠서는 처리할 수 없다. 방법이 두.. 2021. 11. 10.
백준 13717 자바 - 포켓몬 GO (BOJ 13717 JAVA) 문제 : https://www.acmicpc.net/problem/13717 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/13700/BOJ_13717.java 문제에 제시된 '힌트'에서는 하나씩 확인하고 있다. 물론 그렇게 해도 워낙 입력값이 적어서 충분히 가능하지만, 약간만 수식을 넣으면 더 효율좋게 풀 수 있다. Weedle 12 42 위 입력에 대해 보자. k와 m을 입력 받고 m을 k로 나눈 몫으로 현재 몇개 살 수 있는지 알 수 있다. cnt = m/k = 42/12 = 3 (몫) 그리고 m은 m%k (나머지)로 변경한다. 그럼 m = m%k = 6이 된다. 그리고 살 수 있을 때 마다 2개를 되돌려받으므로, 몫*2를 m.. 2021. 11. 10.
백준 1068 자바 - 트리 (BOJ 1068 JAVA) 문제 : https://www.acmicpc.net/problem/1068 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/01000/BOJ_1068.java 제거된 1개가 루트노드일 경우 무조건 0을 출력하면 된다. 그렇지 않다면, 루트노드부터 탐색할 때 제거된 노드쪽으로는 탐색을 진행하지 않으면서 리프노드들의 갯수를 세주면 된다. 로직은 1. 부모 -> 자식으로 단방향 그래프 간선 정보를 저장해둔다. 2. 루트노드부터 갈 수 있는 모든 곳을 탐색하며. 이 때 제거된 노드로는 진입하지 않는다. 3. 탐색 중 리프노드를 발견하면 카운팅한다. 2021. 11. 9.
백준 13711 자바 - LCS 4 (BOJ 13711 JAVA) 문제 : https://www.acmicpc.net/problem/13711 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/13700/BOJ_13711.java [ 스포 주의 ] 직접 풀어보려면 풀이를 보면 안됩니다. 딱 한마디로 바로 풀이가 끝나는 문제라.. --- LCS 시리즈인척 하는 LIS 문제입니다. LCS ; Longest Common Subsequence LIS ; Longest Increasing Subsequence [오답] 1. 문제제목이 LCS라서 처음엔 LCS 알고리즘으로 풀었습니다. -> 답이야 나오겠지만 당연히 메모리초과 (10만x10만xsizeof(int)) 2. 어차피 N x N 배열이 필요없으므로 배열.. 2021. 11. 9.

티스토리툴바