PS/boj (29) 썸네일형 리스트형 [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;.. [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.. [BOJ] 14006 Large Ping Pong Tournament 문제 링크 www.acmicpc.net/problem/14006 풀이 Dudu는 팔씨름의 왕이라서 절대 지지 않는다. 따라서, Dudu는 적당히 자신과 점수가 같거나 낮은 사람과 짝지어서 최종 점수를 따고 이후 모든 라운드에 대해서 0대 0으로 스코어를 내고 팔씨름으로 이기면 조건을 만족한다. N이 0이면 참가자가 Dudu 혼자인데, 이 경우엔 항상 만족한다는 점에 주의하자. Java 코드 더보기 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.List; public class Main { public sta.. [BOJ] 16265 Spreadsheets 문제 링크 www.acmicpc.net/problem/16265 풀이 A는 1, B는 2, C는 3, ..., Z는 26이다. AA는 1*26+1 = 27, AB는 1*26+2 = 28, ..., ZZ는 26*26+26 = 702이다. 자세히 보면 26진법과 관련이 있음을 알 수 있다. 하지만 쓰이는 숫자가 0~25가 아니라 1~26인 상황인데, 이는 오프셋 1을 빼줘서 계산하면 된다. Java 코드 더보기 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws IOExcepti.. 이전 1 2 3 4 다음