PS (33) 썸네일형 리스트형 [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.. [BOJ] 5100 Jean and Joe’s Clothes 문제 링크 www.acmicpc.net/problem/5100 풀이 각 테스트 케이스마다 한 줄에 5개의 수를 출력해야 한다. 첫 번째는 Joe로, 'M' 또는 'L'일 경우에 카운팅한다. 두 번째는 Jean으로, 12 이상일 경우에 카운팅한다. 세 번째는 Jane으로, 12 미만일 경우에 카운팅한다. 네 번째는 James로, 'S'일 경우에 카운팅한다. 다섯 번째는 아무 것도 해당되지 않는 경우로, 'X'일 경우에 카운팅한다. Java 코드 더보기 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.stream.Co.. [BOJ] 20743 Bus Numbers 문제 링크 www.acmicpc.net/problem/20743 풀이 $m$의 최댓값이 40만이므로, 어떤 정수 $x^3+y^3$이 40만 이하인 모든 경우에 대해 생성하여 개수를 센다. 그렇게 2개 이상의 서로 다른 방법으로 나타낼 수 있는 수가 우리가 찾는 정답이다. Java 코드 더보기 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(.. [BOJ] 8711 Odchudzanie 문제 링크 www.acmicpc.net/problem/8711 풀이 naive하게는 $i$번째 인덱스에서 그 뒤에 있는 모든 인덱스 $j$에 대해서 $w_i - w_j$의 최댓값을 구하는 방법이 있다. 이 경우 시간복잡도는 $O(n^2)$이며, 시간 내에 풀 수 없다. 이 문제는 다음과 같은 아이디어로 풀 수 있다. 앞에서부터 쭉 훑다가 지금까지 나온 값 중 가장 큰 값이 나온 상황을 가정하자. 그러면 지금까지 나온 값은 무시하고 최댓값을 선택하는 게 이득이다. $i < j$이고 $w_i - w_j$에서 $w_i$가 크면 클 수록 최적이기 때문이다. 새로운 최댓값이 나왔다면 그 이후부터 등장하는 최솟값을 찾아야 한다. 그 이전에 등장한 최솟값은 쓸모가 없어지기 때문이다. 이런 방식으로 풀면 시간복잡도는 .. [프로그래머스] Level 2 숫자의 표현 문제 링크 programmers.co.kr/learn/courses/30/lessons/12924 풀이 1 $n$을 $k$개의 연속된 자연수의 합으로 나타낼 수 있는지 확인하려면 어떻게 해야할까? 차근차근 따져보도록 하자. $k$가 1이라면 $n$ 자기 자신으로 표현된다. $k$가 2라면 어떤 자연수 $m$과 $m+1$에 대해서 $n=m+m+1$이 성립해야 한다. 이는 $n$에서 1을 빼고 2로 나누어 떨어지는지 확인하면 된다. $k$가 3이라면 어떤 자연수 $m$, $m+1$, $m+2$에 대해서 $n=m+m+1+m+2$가 성립해야 한다. 이는 $n$에서 $1+2$를 빼고 3으로 나누어 떨어지는지 확인하면 된다. 규칙이 보이는가? 즉, $n$에서 1+2+...+k-1을 빼고 $k$로 나누어 떨어지는지 .. [BOJ] 19774 ABCD-код 문제 링크 www.acmicpc.net/problem/19774 풀이 입력받은 4자리의 수를 2자리씩 끊어서 제곱하고 더해야 한다. 이는 각각 100으로 나눈 몫과 나머지를 통해 구할 수 있다. Java 코드 더보기 import java.io.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); int T = Integer.parseInt(in.readLine()); StringBuilder out = new StringBuilder(); while (T-- > 0) { int n.. [BOJ] 8965 Circular Sequence 문제 링크 www.acmicpc.net/problem/8965 풀이 문자열로 만들 수 있는 모든 경우의 수에 대해 어떤 경우가 가장 사전순으로 앞서는지 구하면 된다. Java 코드 더보기 import java.io.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); int T = Integer.parseInt(in.readLine()); StringBuilder out = new StringBuilder(); while (T-- > 0) { String s = in.readLin.. [프로그래머스] Level 2 다음 큰 숫자 문제 링크 programmers.co.kr/learn/courses/30/lessons/12911 풀이 n+1부터 시작해서 1씩 증가시키며 켜진 비트의 수가 같은 경우를 찾으면 된다. 이렇게 풀 경우 최악의 경우는 어떻게 될까? 대강 따져보자면 n은 최대 100만이므로 사용되는 비트의 수는 많아봤자 20개다. 20개의 비트를 재조정하는 것으로 항상 모든 답이 나올 수 있으니 연산의 수는 $2^{20}$을 넘지 않는다. C++ 코드 더보기 프로그래머스는 clang++으로 컴파일한다. gcc나 clang에는 켜진 비트의 수를 구하는 내장함수인 __builtin_popcount라는 함수가 있다. int solution(int n) { int cnt = __builtin_popcount(n); for (int .. 이전 1 2 3 4 5 다음