본문 바로가기

백준749

백준 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.
백준 16964 자바 - DFS 스페셜 저지 (BOJ 16964 JAVA) 문제 링크 : https://www.acmicpc.net/problem/16964 코드 링크 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/16900/BOJ_16964.java 해결 방식을 떠올리기 다소 어려웠다. 결국 올바른 DFS 방문 순서라 함은 '각 간선을 방문하는 순서는 상관없지만 어쨌든 방문할 간선이 남아 있다면 무조건 방문해야 한다.' 이걸 지키면된다. 예를 들어 아래와 같은 그래프를 보자. 1부터 시작한다. 방문한 곳은 빨간색으로 표시했다. 1에서 2부터 가야할까 3부터 가야할까? 상관없다. 우선 2로 가보겠다. 이 때, 3을 가면 올바른 DFS 순서가 아니게 된다. 2로 일단 갔으면 2에 연결된 간선을 모두 들린 후 3으.. 2021. 11. 9.

티스토리툴바