Etc
[코테후기] 2022 원티드 3rd 쇼미더코드(+코드)
하다보면 되겠지
2023. 1. 14. 17:38
오늘 오후 2~5시에 진행됐던 쇼미더코드가 끝났다. 결론은 세 문제 다 풀긴 풀었다! 와아아 👏 A는 부분합 문제, B는 BFS 문제, C는 dp 문제였다. 공개된 문제를 보니 난이도는 골드5, 5, 3이었다. 직접 풀어보고 싶으신 분들은 이쪽 → https://www.acmicpc.net/category/detail/3451
사실 A번부터 풀기 시작했는데 처음에 잘 안풀리길래 그냥 관둘까 하다가 B번이 너무 쉬워보여서 조금만 더 해보자 했다. 다행히 B번은 1트만에 풀었는데 그게 이미 대회가 시작된지 1시간 30분이 지난 뒤여서 좀 아쉬웠다. C번은 처음에 문제를 이해하는 데 시간이 좀 걸렸고, 전체 틀을 금방 잡았는데 사소하게 놓친 부분들이 있어 이것저것 고치다보니 제출횟수가 좀 많아졌다. C번까지 풀고 나니 20분정도가 남았고, A번을 다시 보는데 갑자기 그제서야 방법이 확 생각나서.. 후다닥 풀고 종료 5분 전에 다 제출했다. 아래 코드는 급하게 푼 만큼, 가독성이나 효율성이 안좋을 수 있는 점 참고 바란다.
+
1월 30일에 테스트 결과가 이메일로 발송됐다. 제출 횟수나 시간 등을 봤을 때 금손은 절대 아닐거라 생각하고 있었고, 예상대로 은손을 받았다.
A번: 신을 모시는 사당
입력된 1의 개수, 2의 개수를 카운팅해서 배열에 넣도록 했다. 1은 음수, 2는 양수로 해서 가장 큰/작은 연속된 수열의 합을 구하는 로직을 적용했다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
ArrayList<Integer> arr = new ArrayList<>();
int sum = 0;
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
int val = Integer.parseInt(st.nextToken());
if(val == 1){
if(sum < 0) sum--;
else{
arr.add(sum);
sum = -1;
}
}
else{
if(sum > 0) sum++;
else{
arr.add(sum);
sum = 1;
}
}
}
arr.add(sum);
int arrSize = arr.size();
int largeSum = 0, smallSum = 0;
int largest = 0, smallest = 0;
for (int i = 0; i < arrSize; i++) {
for (int j = i; j < arrSize; j++) {
largeSum += arr.get(j);
smallSum += arr.get(j);
largest = Math.max(largest, largeSum);
smallest = Math.min(smallest, smallSum);
}
largeSum = smallSum = 0;
}
int answer = Math.max(largest, -smallest);
System.out.println(answer);
}
}
B번: 도넛 행성
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static class Pos{
int x, y;
Pos(int x, int y){
this.x = x;
this.y = y;
}
}
static int N, M;
static int[] dx = {-1, 0, 1, 0};
static int[] dy = {0, 1, 0, -1};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = null;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
int[][] star = new int[N][M];
boolean[][] visited = new boolean[N][M];
for(int i = 0;i < N;i++){
st = new StringTokenizer(br.readLine());
for(int j = 0;j < M;j++){
star[i][j] = Integer.parseInt(st.nextToken());
if(star[i][j] == 1) visited[i][j] = true;
}
}
int answer = 0;
for(int i = 0;i < N;i++) {
for (int j = 0; j < M; j++) {
if(visited[i][j]) continue;
bfs(i, j, visited);
answer++;
}
}
System.out.println(answer);
}
private static void bfs(int i, int j, boolean[][] visited) {
Queue<Pos> q = new LinkedList();
q.add(new Pos(i, j));
while(!q.isEmpty()){
Pos cur = q.poll();
if(visited[cur.x][cur.y]) continue;
visited[cur.x][cur.y] = true;
for(int d = 0;d < 4;d++){
int nx = cur.x + dx[d];
int ny = cur.y + dy[d];
// set bound
if(nx >= N) nx -= N;
else if(nx < 0) nx += N;
if(ny >= M) ny -= M;
else if(ny < 0) ny += M;
if(!visited[nx][ny])
q.add(new Pos(nx, ny));
}
}
}
}
C번: 미팅
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = null;
st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int C = Integer.parseInt(st.nextToken());
int[][] W = new int[C+1][C+1];
int[] aChar = new int[N];
int[] bChar = new int[M];
// 성격 간의 만족도 저장
for (int i = 1; i <= C; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 1; j <= C; j++) {
W[i][j] = Integer.parseInt(st.nextToken());
}
}
// A와 B 학생들의 성격 저장
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++)
aChar[i] = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
for (int i = 0; i < M; i++)
bChar[i] = Integer.parseInt(st.nextToken());
// dp 초기값 설정
long[][] dp = new long[N][M];
long answer = 0;
dp[0][0] = W[aChar[0]][bChar[0]];
for (int i = 1; i < N; i++)
dp[i][0] = Math.max(dp[i-1][0], W[aChar[i]][bChar[0]]);
for (int i = 1; i < M; i++)
dp[0][i] = Math.max(dp[0][i-1], W[aChar[0]][bChar[i]]);
// 최대 만족도 계산
for (int i = 1; i < N; i++) {
for (int j = 1; j < M; j++) {
// 악수를 하는 경우와 안하는 경우 고려
long val = Math.max(dp[i-1][j], dp[i][j-1]);
dp[i][j] = Math.max(val, dp[i-1][j-1] + W[aChar[i]][bChar[j]]);
}
}
System.out.println(dp[N-1][M-1]);
}
}