백준 2309번 일곱 난쟁이
문제
나의 풀이
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int a[] = new int[9];
int sum = 0;
for(int i = 0; i < 9; i++) {
a[i] = sc.nextInt();
sum += a[i];
}
Arrays.sort(a);
for(int i = 0; i < 9; i++) {
for(int j = i + 1; j < 9; j++) {
if(sum - a[i] - a[j] == 100) {
for(int k = 0; k < 9; k++) {
if(k == i || k == j) {
continue;
}
System.out.println(a[k]);
}
return;
}
}
}
}
}9명의 난쟁이 중에서 난쟁이가 아닌 2명을 찾으면 되기 때문에
경우의 수는, 9C2가 되고 36이다.
우선 난쟁이들의 키를 저장할 배열 a를 생성해서 난쟁이 키들을 입력 받아 저장시켜준다. 그와 동시에 sum 변수에 난쟁이들의 키의 합을 구해준다.
배열 a를 정렬하고
i를 0부터 8까지 for문을 돌리고 이중 포문으로 j를 i보다 1큰 값 부터 8까지 for문을 돌려준다. 이때 sum에서 a의 i번째 요소와 a의 j번째 요소를 뺐을 때 100이 되면 이 둘을 제외한 나머지가 난쟁이란 뜻이므로 for문을 k 0부터 8까지 돌려서 k가 i거나 j인 경우를 제외하고 키를 출력하게 하면 된다.
결과
백준 3085번 사탕 게임
문제
나의 풀이
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
char a[][] = new char[n][n];
for(int i = 0; i < n; i++) {
a[i] = sc.next().toCharArray();
}
int answer = 0;
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
if(j + 1 < n) { // 오른쪽과 바꾸기
char t = a[i][j];
a[i][j] = a[i][j + 1];
a[i][j + 1] = t;
int r = check(a);
answer = Math.max(answer, r);
t = a[i][j];
a[i][j] = a[i][j + 1];
a[i][j + 1] = t;
}
if(i + 1 < n) { // 아래쪽과 바꾸기
char t = a[i][j];
a[i][j] = a[i + 1][j];
a[i + 1][j] = t;
int r = check(a);
answer = Math.max(answer, r);
t = a[i][j];
a[i][j] = a[i + 1][j];
a[i + 1][j] = t;
}
}
}
System.out.println(answer);
}
static int check(char a[][]) {
int n = a.length;
int answer = 1;
for(int i = 0; i < n; i++) {
int count = 1;
for(int j = 1; j < n; j++) { // 행 계산
if(a[i][j] == a[i][j - 1]) {
count += 1;
} else {
count = 1;
}
answer = Math.max(answer, count);
}
count = 1;
for(int j = 1; j < n; j++) { // 열 계산
if(a[j][i] == a[j - 1][i]) {
count += 1;
} else {
count = 1;
}
answer = Math.max(answer, count);
}
}
return answer;
}
}경우의 수는 인접한 두 칸을 고르는 방법의 수는 O(N2)이다.
그 다음, 같은 색으로 이루어져 있는 가장 긴 연속 부분 행 또는 열을 고르는 것도 O(N2)이다.
따라서, 최종적으로 O(N4)이다.
먼저 오른쪽과 값을 바꿔보고 이 상태로 행을 계산해본 뒤 열까지 계산해서 가장 큰 값을 answer 변수에 저장하고 값을 원 상태로 복귀시킨다.
그런 다음 아래쪽과 값을 바꿔보고 이 상태로 행을 계산해본 뒤 열까지 계산하고 가장 큰 값을 answer 변수에 저장하고 값을 원 상태로 복귀시킨다.
마지막에는 answer 값을 출력시키면 된다.
결과
백준 1476번 날짜 계산
문제
나의 풀이
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int e = sc.nextInt();
int s = sc.nextInt();
int m = sc.nextInt();
int a = 1, b = 1, c = 1;
for(int i = 1; ; i++) {
if(a == e && b == s && c == m) {
System.out.println(i);
break;
}
a += 1;
b += 1;
c += 1;
if(a == 16) {
a = 1;
}
if(b == 29) {
b = 1;
}
if(c == 20) {
c = 1;
}
}
}
}경우의 수는 E(15) x S(28) x M(19) = 7980이다. 따라서, 시간 안에 가능하다.
결과
백준 1107번 리모컨
문제
나의 풀이
import java.util.*;
public class Main {
static boolean broken[] = new boolean[10];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
for(int i = 0; i < m; i++) {
int x = sc.nextInt();
broken[x] = true;
}
int answer = Math.abs(n - 100);
for(int i = 0; i <= 1000000; i++) {
int c = i;
int len = possible(c);
if(len > 0) {
int press = Math.abs(c - n);
answer = Math.min(answer, len + press);
}
}
System.out.println(answer);
}
static int possible(int c) {
if(c == 0) {
if(broken[0]) {
return 0;
} else {
return 1;
}
}
int len = 0;
while(c > 0) {
if(broken[c % 10]) {
return 0;
}
len += 1;
c /= 10;
}
return len;
}
}숫자 버튼을 누르고 그 다음 +나 -중 하나만 연속해서 눌러야 최소값을 구할 수 있다.
- 이동할 채널 C를 정한다.
- C에 포함되어있는 숫자 중에 고장난 버튼이 있는지 확인한다.
- 고장난 버튼이 포함되어 있지 않다면 |C-N|을 계산해 +나 -버튼을 몇번 눌러야 하는지를 계산한다.
결과
가보자고