import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
boolean[] visited = new boolean[n];
int[] result = new int[m];
combination(n, m, 0, visited, result);
}
static void combination(int n, int m, int num, boolean[] visited, int[] result) {
if (num == m) {
for (int i = 0; i < m; i++) {
System.out.print(result[i] + " ");
}
System.out.println();
}
else {
for (int i = 0; i < n; i++) {
if(!visited[i]) {
if(num != 0) {
if (result[num - 1] < i + 1) {
visited[i] = true;
result[num] = i + 1;
}
else continue;
}
else {
visited[i] = true;
result[num] = i + 1;
}
combination(n, m, num + 1, visited, result);
visited[i] = false;
}
}
}
}
}
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
boolean[] visited = new boolean[n];
int[] result = new int[m];
permutation(n, m, 0, visited, result);
}
static void permutation(int n, int m, int num, boolean[] visited, int[] result) {
if (num == m) {
for (int i = 0; i < m; i++) {
System.out.print(result[i] + " ");
}
System.out.println();
return;
}
for (int i = 0; i < n; i++) {
if(!visited[i]) {
visited[i] = true;
result[num] = i + 1;
permutation(n, m, num + 1, visited, result);
visited[i] = false;
}
}
}
}
순열을 구하는 방법을 모른다면 어려웠을 문제지만 순열을 공부했기 때문에 쉽게 풀 수 있었다.
7개월 뒤 8월 16일에 어떠한 것도 보지 않고 다시 풀어보았다. 이번엔 C++로 풀어봤다.
#include <vector>
#include <iostream>
using namespace std;
int n, m;
void permutation(int num, vector<bool> visited, vector<int> result) {
if (num == m) {
for (int i = 0; i < result.size(); i++) {
cout << result[i] << " ";
}
cout << '\n';
return;
}
for (int i = 1; i <= n; i++) {
if (!visited[i]) {
result[num] = i;
visited[i] = true;
permutation(num + 1, visited, result);
visited[i] = false;
}
}
}
int main() {
cin >> n >> m;
vector<bool> visited(n + 1, false);
vector<int> result(m);
permutation(0, visited, result);
system("pause");
return 0;
}
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
int[][] arr = new int[n][m];
int[][] ori = new int[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
arr[i][j] = in.nextInt();
ori[i][j] = arr[i][j];
}
}
int max = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (arr[i][j] == 1 || arr[i][j] == 2) continue;
for (int k = i; k < n; k++) {
for (int l = 0; l < m; l++) {
if (k == i && j >= l) continue;
if (arr[k][l] == 1 || arr[k][l] == 2) continue;
int count = 0;
for (int o = k; o < n; o++) {
for (int p = 0; p < m; p++) {
if (o == k && p <= l) continue;
if (arr[o][p] == 1 || arr[o][p] == 2) continue;
arr[i][j] = 1;
arr[k][l] = 1;
arr[o][p] = 1;
for (int a = 0; a < n; a++) {
for (int b = 0; b < m; b++) {
if (arr[a][b] == 2) {
if (a == 0 && b == 0) {
if (arr[a + 1][b] == 0) arr[a + 1][b] = 2;
if (arr[a][b + 1] == 0) arr[a][b + 1] = 2;
} else if (a == 0 && b == m - 1) {
if (arr[a + 1][b] == 0) arr[a + 1][b] = 2;
if (arr[a][b - 1] == 0) arr[a][b - 1] = 2;
} else if (a == n - 1 && b == 0) {
if (arr[a - 1][b] == 0) arr[a - 1][b] = 2;
if (arr[a][b + 1] == 0) arr[a][b + 1] = 2;
} else if (a == n - 1 && b == m - 1) {
if (arr[a - 1][b] == 0) arr[a - 1][b] = 2;
if (arr[a][b - 1] == 0) arr[a][b - 1] = 2;
} else if (a == 0) {
if (arr[a + 1][b] == 0) arr[a + 1][b] = 2;
if (arr[a][b + 1] == 0) arr[a][b + 1] = 2;
if (arr[a][b - 1] == 0) arr[a][b - 1] = 2;
} else if (b == 0) {
if (arr[a + 1][b] == 0) arr[a + 1][b] = 2;
if (arr[a - 1][b] == 0) arr[a - 1][b] = 2;
if (arr[a][b + 1] == 0) arr[a][b + 1] = 2;
} else if (a == n - 1) {
if (arr[a][b - 1] == 0) arr[a][b - 1] = 2;
if (arr[a - 1][b] == 0) arr[a - 1][b] = 2;
if (arr[a][b + 1] == 0) arr[a][b + 1] = 2;
} else if (b == m - 1) {
if (arr[a + 1][b] == 0) arr[a + 1][b] = 2;
if (arr[a][b - 1] == 0) arr[a][b - 1] = 2;
if (arr[a - 1][b] == 0) arr[a - 1][b] = 2;
} else {
if (arr[a + 1][b] == 0) arr[a + 1][b] = 2;
if (arr[a - 1][b] == 0) arr[a - 1][b] = 2;
if (arr[a][b + 1] == 0) arr[a][b + 1] = 2;
if (arr[a][b - 1] == 0) arr[a][b - 1] = 2;
}
}
}
}
for (int a = n - 1; a >= 0; a--) {
for (int b = m - 1; b >= 0; b--) {
if (arr[a][b] == 2) {
if (a == 0 && b == 0) {
if (arr[a + 1][b] == 0) arr[a + 1][b] = 2;
if (arr[a][b + 1] == 0) arr[a][b + 1] = 2;
} else if (a == 0 && b == m - 1) {
if (arr[a + 1][b] == 0) arr[a + 1][b] = 2;
if (arr[a][b - 1] == 0) arr[a][b - 1] = 2;
} else if (a == n - 1 && b == 0) {
if (arr[a - 1][b] == 0) arr[a - 1][b] = 2;
if (arr[a][b + 1] == 0) arr[a][b + 1] = 2;
} else if (a == n - 1 && b == m - 1) {
if (arr[a - 1][b] == 0) arr[a - 1][b] = 2;
if (arr[a][b - 1] == 0) arr[a][b - 1] = 2;
} else if (a == 0) {
if (arr[a + 1][b] == 0) arr[a + 1][b] = 2;
if (arr[a][b + 1] == 0) arr[a][b + 1] = 2;
if (arr[a][b - 1] == 0) arr[a][b - 1] = 2;
} else if (b == 0) {
if (arr[a + 1][b] == 0) arr[a + 1][b] = 2;
if (arr[a - 1][b] == 0) arr[a - 1][b] = 2;
if (arr[a][b + 1] == 0) arr[a][b + 1] = 2;
} else if (a == n - 1) {
if (arr[a][b - 1] == 0) arr[a][b - 1] = 2;
if (arr[a - 1][b] == 0) arr[a - 1][b] = 2;
if (arr[a][b + 1] == 0) arr[a][b + 1] = 2;
} else if (b == m - 1) {
if (arr[a + 1][b] == 0) arr[a + 1][b] = 2;
if (arr[a][b - 1] == 0) arr[a][b - 1] = 2;
if (arr[a - 1][b] == 0) arr[a - 1][b] = 2;
} else {
if (arr[a + 1][b] == 0) arr[a + 1][b] = 2;
if (arr[a - 1][b] == 0) arr[a - 1][b] = 2;
if (arr[a][b + 1] == 0) arr[a][b + 1] = 2;
if (arr[a][b - 1] == 0) arr[a][b - 1] = 2;
}
}
}
}
count = 0;
for (int a = 0; a < n; a++) {
for (int b = 0; b < m; b++) {
if(arr[a][b] == 0) count++;
}
}
if(count > max) {
max = count;
}
for (int a = 0; a < n; a++) {
for (int b = 0; b < m; b++) {
arr[a][b] = ori[a][b];
}
}
}
}
}
}
}
}
System.out.println(max);
}
}
살다살다 8중 for문을 쓸 줄이야 내가 조합(Combination)을 코드로 구현할 줄 몰라서 무식한 방법으로 했다
예제 입력을 입력으로 넣었을 때는 모두 옳은 답이 나오는데 제출하면 틀리다고 한다.
예제 입력1예제 입력2예제 입력3
아직도 못 풀었지만 꼭 내 손으로 풀 거다
2020.01.14
이후에 순열과 조합 알고리즘을 공부하고 오늘 다시 도전해보았다
def permutation(result, num, n, li):
if num == 3:
v = [[False] * m for i in range(n)]
import collections
q = collections.deque()
for i in virus:
q.append((i[0], i[1]))
while q:
cur = q.popleft()
v[cur[0]][cur[1]] = True
if cur[0] - 1 >= 0 and li[cur[0] - 1][cur[1]] == 0 and not v[cur[0] - 1][cur[1]]:
q.append((cur[0] - 1, cur[1]))
if cur[0] + 1 < n and li[cur[0] + 1][cur[1]] == 0 and not v[cur[0] + 1][cur[1]]:
q.append((cur[0] + 1, cur[1]))
if cur[1] - 1 >= 0 and li[cur[0]][cur[1] - 1] == 0 and not v[cur[0]][cur[1] - 1] :
q.append((cur[0], cur[1] - 1))
if cur[1] + 1 < m and li[cur[0]][cur[1] + 1] == 0 and not v[cur[0]][cur[1] + 1]:
q.append((cur[0], cur[1] + 1))
count = 0
for i in range(n):
for j in range(m):
if li[i][j] == 0 and not v[i][j]:
count += 1
c.append(count)
return
for i in range(n):
for j in range(m):
if not visited[i][j]:
if li[i][j] == 0:
if num > 0:
if result[num - 1][0] < i:
result[num] = (i, j)
visited[i][j] = True
li[i][j] = 1
permutation(result, num + 1, n, li)
visited[i][j] = False
li[i][j] = 0
elif result[num - 1][0] == i and result[num - 1][1] < j:
result[num] = (i, j)
visited[i][j] = True
li[i][j] = 1
permutation(result, num + 1, n, li)
visited[i][j] = False
li[i][j] = 0
else:
continue
else:
result[num] = (i, j)
visited[i][j] = True
li[i][j] = 1
permutation(result, num + 1, n, li)
visited[i][j] = False
li[i][j] = 0
from sys import stdin
n, m = list(map(int, stdin.readline().split()))
li = []
virus = []
for i in range(n):
temp = list(map(int, stdin.readline().split()))
li.append(temp)
for j in range(m):
if temp[j] == 2:
virus.append((i, j))
visited = [[False] * m for i in range(n)]
r = [(0, 0)] * 3
c = []
permutation(r, 0, n, li)
print(max(c))
시간초과가 뜬다... 조합이 재귀함수라서 그런걸까
6시간 뒤
성공! 위와 코드는 똑같은데 큐에 들어가 있는 것을 중복으로 집어넣는 것을 방지해주었더니 바로 해결됐다.
오늘 또 교훈을 얻는다. 큐에 넣을 때 visited를 True로 바꾸자
def permutation(result, num, n, li):
if num == 3:
v = [[False] * m for i in range(n)]
import collections
q = collections.deque()
for i in virus:
q.append((i[0], i[1]))
while q:
cur = q.popleft()
if not v[cur[0]][cur[1]] and li[cur[0]][cur[1]] == 0:
v[cur[0]][cur[1]] = True
if cur[0] - 1 >= 0 and li[cur[0] - 1][cur[1]] == 0 and not v[cur[0] - 1][cur[1]]:
q.append((cur[0] - 1, cur[1]))
v[cur[0] - 1][cur[1]] = True
if cur[0] + 1 < n and li[cur[0] + 1][cur[1]] == 0 and not v[cur[0] + 1][cur[1]]:
q.append((cur[0] + 1, cur[1]))
v[cur[0] + 1][cur[1]] = True
if cur[1] - 1 >= 0 and li[cur[0]][cur[1] - 1] == 0 and not v[cur[0]][cur[1] - 1] :
q.append((cur[0], cur[1] - 1))
v[cur[0]][cur[1] - 1] = True
if cur[1] + 1 < m and li[cur[0]][cur[1] + 1] == 0 and not v[cur[0]][cur[1] + 1]:
q.append((cur[0], cur[1] + 1))
v[cur[0]][cur[1] + 1] = True
count = 0
for i in range(n):
for j in range(m):
if li[i][j] == 0 and not v[i][j]:
count += 1
c.append(count)
return
for i in range(n):
for j in range(m):
if not visited[i][j]:
if li[i][j] == 0:
if num > 0:
if result[num - 1][0] < i:
result[num] = (i, j)
visited[i][j] = True
li[i][j] = 1
permutation(result, num + 1, n, li)
visited[i][j] = False
li[i][j] = 0
elif result[num - 1][0] == i and result[num - 1][1] < j:
result[num] = (i, j)
visited[i][j] = True
li[i][j] = 1
permutation(result, num + 1, n, li)
visited[i][j] = False
li[i][j] = 0
else:
continue
else:
result[num] = (i, j)
visited[i][j] = True
li[i][j] = 1
permutation(result, num + 1, n, li)
visited[i][j] = False
li[i][j] = 0
from sys import stdin
n, m = list(map(int, stdin.readline().split()))
li = []
virus = []
for i in range(n):
temp = list(map(int, stdin.readline().split()))
li.append(temp)
for j in range(m):
if temp[j] == 2:
virus.append((i, j))
visited = [[False] * m for i in range(n)]
r = [(0, 0)] * 3
c = []
permutation(r, 0, n, li)
print(max(c))
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int[] arr = new int[1000001];
arr[1] = 1;
arr[2] = 2;
for (int i = 3; i < 1000001; i++) {
arr[i] = arr[i - 2] + arr[i - 1];
}
System.out.print(arr[n] % 15746);
}
}
이렇게 했는데 자꾸 틀렸다는거다
아무리 봐도 맞는데 뭐가 틀리다는건지 몰라서 너무 답답했지만 그래도 스스로 풀어내겠다는 오기로 풀었다
그런데도 계속 틀리다는거다
그래서 결국 구글링을 해봤더니 다들 저장할 때부터 15746으로 나눈 나머지를 저장하더라
설마 하고 똑같은 코드에 % 15746 이것만 붙여서 했더니 맞았다고 떴다.
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int[] arr = new int[1000001];
arr[1] = 1;
arr[2] = 2;
for (int i = 3; i < 1000001; i++) {
arr[i] = arr[i - 2] % 15746 + arr[i - 1] % 15746;
}
System.out.print(arr[n] % 15746);
}
}
너무 허무했다.
길이가 N인 2진 수열의 개수를 15746으로 나눈 나머지를 출력하라고 해서 출력할 때만 15746으로 나눈 나머지를 출력했는데 왜 저장할 때도 15746으로 나눈 나머지를 저장해야 하는지 모르겠었다.
그런데 생각해보니 피보나치 수열은 기하급수적으로 증가하기 때문에 오버플로우가 난다.
int로 하면 47번째부터, long으로 해도 93번째부터 오버플로우가 난다.
따라서 애초에 저장할 때 나머지를 저장해주어 오버플로우를 방지한 것이다.
몇 분만에 푼 문제를 괜히 몇 시간 시간낭비했다는 생각이 들었었지만 덕분에 깨달은 게 있으니 다행인 것 같다. 다음부턴 이런 실수 하지 말아야지.
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
ArrayList list = new ArrayList<>();
for (int i = 0; i < 3000000; i++) {
if(String.valueOf(i).contains("666"))
list.add(i);
}
System.out.println(list.get(n - 1));
}
}
처음에는
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
String s = "666";
HashSet set = new HashSet<>();
for (int i = 0; i < 10000; i++) {
if(String.valueOf(i).length() == 1) {
set.add(Integer.parseInt(s + i));
set.add(Integer.parseInt(i + s));
}
else if (String.valueOf(i).length() == 2) {
set.add(Integer.parseInt(s + i));
set.add(Integer.parseInt(i + s));
set.add(Integer.parseInt(String.valueOf(i).charAt(0) + s + String.valueOf(i).charAt(1)));
}
else if (String.valueOf(i).length() == 3) {
set.add(Integer.parseInt(s + i));
set.add(Integer.parseInt(i + s));
set.add(Integer.parseInt(String.valueOf(i).charAt(0) + s + String.valueOf(i).substring(1, 3)));
set.add(Integer.parseInt(String.valueOf(i).substring(0, 2) + s + String.valueOf(i).charAt(2)));
}
else {
set.add(Integer.parseInt(s + i));
set.add(Integer.parseInt(i + s));
set.add(Integer.parseInt(String.valueOf(i).charAt(0) + s + String.valueOf(i).substring(1, 4)));
set.add(Integer.parseInt(String.valueOf(i).substring(0, 2) + s + String.valueOf(i).substring(2, 4)));
set.add(Integer.parseInt(String.valueOf(i).substring(0, 3) + s + String.valueOf(i).charAt(3)));
}
}
ArrayList list = new ArrayList<>(set);
list.sort((a, b) -> a - b);
System.out.println(list.get(n - 1));
}
}
이렇게 했는데 자꾸 틀렸다고 나오는거다.
그래서 포기하고 구글링을 해봤더니 자바의 String 클래스에 contains()라는 메소드가 있었다.
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
char[][] arr = new char[n][m];
String[] starr = new String[n];
for (int i = 0; i < n; i++) {
starr[i] = in.next();
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
arr[i][j] = starr[i].charAt(j);
}
}
int min = 2500;
//첫번째 칸이 흰색인 경우 case1
//첫번째 칸이 검은색인 경우 case2
for (int i = 0; i <= n - 8; i++) {
for (int j = 0; j <= m - 8; j++) {
int case1 = 0;
int case2 = 0;
for (int k = 0; k < 8; k++) {
for (int l = 0; l < 8; l++) {
if (arr[i + k][j + l] == 'W') {
if (k % 2 == 0 && l % 2 == 0) {
case2++;
}
else if (k % 2 == 0 && l % 2 == 1) {
case1++;
}
else if (k % 2 == 1 && l % 2 == 0) {
case1++;
}
else {
case2++;
}
}
else {
if (k % 2 == 0 && l % 2 == 0) {
case1++;
}
else if (k % 2 == 0 && l % 2 == 1) {
case2++;
}
else if (k % 2 == 1 && l % 2 == 0) {
case2++;
}
else {
case1++;
}
}
}
}
if (case1 < min) {
min = case1;
}
if (case2 < min) {
min = case2;
}
}
}
System.out.println(min);
}
}
