PS 일기장 (39) 썸네일형 리스트형 [BOJ] 19236 청소년 상어 문제 링크 www.acmicpc.net/problem/19236 풀이 문제에서 요구하는 내용을 그대로 구현하면 되는 구현 문제. 백트랙킹을 이용해 모든 경우의 수를 따져가며 최댓값을 구하면 된다. 이 경우 시간복잡도는 괜찮을까? 처음에 (0, 0) 위치의 물고기를 잡아먹고 시작하므로 남은 물고기는 15마리이며 상어가 움직이는 경우의 수는 많아봤자 3번이다. 따라서 적당히 최악의 연산량을 계산해도 $3^{15}$이며(실제로는 이보다 더 작다), 약 1400만 가량이므로 충분하다. C++ 코드 더보기 #include #define X first #define Y second #define sz(x) int(size(x)) #define all(x) x.begin(), x.end() #define ini(x,.. [BOJ] 1323 숫자 연결하기 문제 링크 www.acmicpc.net/problem/1323 풀이 $N$의 길이를 $l$이라고 한다면 $N$에 $N$을 이어붙인 결과는 $N * 10^l + N$으로 표현할 수 있다. 이 값이 $K$로 나누어 떨어지는지 확인하는 것은 법 $K$에 대해 0과 합동인지 확인하는 것과 같다. 따라서, $K$로 나눈 나머지를 이용하여 0이 나올 때까지 계산을 진행하면서 횟수를 세면 된다. 이때 이미 나왔던 수가 다시 등장하면 그것은 $K$의 배수가 될 수 없음을 뜻한다. Java 코드 더보기 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokeniz.. [BOJ] 17211 좋은 날 싫은 날 문제 링크 www.acmicpc.net/problem/17211 풀이 기분 좋은 날의 다음 날이 기분 좋을 확률을 $p_1$ 기분 좋은 날의 다음 날이 기분 싫을 확률을 $p_2$ 기분 나쁜 날의 다음 날이 기분 좋을 확률을 $p_3$ 기분 나쁜 날의 다음 날이 기분 나쁠 확률을 $p_4$ 이라고 하자. $n-1$일 뒤의 기분 좋을 확률을 $q_{n-1}$이라고 하면 기분 나쁠 확률은 $1 - q_{n-1}$이다. 따라서, $q_n = q_{n-1} * p_1 + (1 - q_{n-1}) * p_3$으로 구할 수 있다. Java 코드 더보기 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader;.. [Java] private final vs final private 개요 클래스 내부에서만 사용하기 위해 private, 상수로써 사용하기 위해 final을 쓰고자 할 때 어떤 순서로 쓰는 것이 맞을까? 순서가 달라짐에 따라 어떤 차이가 있을까? 차이는 없다 일단, 둘의 차이는 전혀 없다. 완벽하게 동일한 의미이다. 하지만 차이가 없다고 해서 어떤 때는 private final로 쓰고, 어떤 때는 final private으로 쓰면 통일성도 없고 어수선해 보일 것이다. 이런 순서에 대한 컨벤션은 무엇일까? 정답은 자바 스펙에 구글의 자바 스타일 가이드도, OpenJDK 커뮤니티에서 만든 스타일 가이드도 모두 자바 스펙에서 써준 순서를 따를 것을 권장하고 있다. 자바 스펙에 따르면 private final로 쓰는 것이 바람직하다. 관련 링크 stackoverflow.com/.. [BOJ] 16952 체스판 여행 2 문제 링크 www.acmicpc.net/problem/16952 풀이 체스판의 크기가 최대 10 by 10이고 말의 개수가 3개이므로 상태공간의 크기는 300으로 나타낼 수 있다. 한 상태에서 다른 상태로 가는 최단 거리를 다익스트라로 구하고 이를 그래프로 구축한 뒤 플로이드 워셜을 썼다. 당연히 최적의 풀이는 아니며, 매우 비효율적인 풀이지만 그래도 통과는 된다. C++ 코드 더보기 #include #define X first #define Y second #define sz(x) int(size(x)) #define all(x) x.begin(), x.end() #define ini(x, y) memset(x, y, sizeof(x)) #define endl '\n' #define fastio cin.. [BOJ] 10497 Hitting the Targets 문제 링크 www.acmicpc.net/problem/10497 풀이 쿼리로 들어오는 좌표를 다른 모든 네모와 원에 대해 포함관계를 확인하면서 카운팅하면 된다. Java 코드 더보기 코딩하다 보니까 나도 모르게 객체지향적으로 짜고 있는 나를 발견했다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.List; import java.util.StringTokenizer; interface Shape { boolean contains(int x, int y); } class Rectangle implements .. [BOJ] 15487 A[j]-A[i]+A[l]-A[k] 문제 링크 www.acmicpc.net/problem/15487 풀이 1 dp 테이블을 다음과 같이 정의한다. dp[n]: [0, n] 구간에서 두 인덱스 i, j (i < j)를 선택했을 때 A[j] - A[i]의 최댓값 prefix는 이렇게 완성하고, suffix dp는 만들어도 상관없지만 뒤에서부터 순회하면서 온라인으로 처리할 수 있다. 그렇게 두 구간의 최댓값을 더하면 답이 된다. 이 풀이는 시간복잡도와 공간복잡도 둘다 $O(N)$이다. C++ 코드 더보기 #include #define X first #define Y second #define sz(x) (int)size(x) #define all(x) x.begin(), x.end() #define ini(x, y) memset(x, y, si.. [프로그래머스] Level 2 124 나라의 숫자 문제 링크 programmers.co.kr/learn/courses/30/lessons/12899 풀이 [BOJ] 16265 Spreadsheets 문제와 매우 유사하다. 3진법처럼 계산하되 오프셋 계산을 해주면 된다. C++ 코드 더보기 #include using namespace std; string solution(int n) { string ret; for (; n; n = (n - 1) / 3) ret += "124"[(n - 1) % 3]; reverse(ret.begin(), ret.end()); return ret; } 이전 1 2 3 4 5 다음