첫 번째 시도

import java.util.Scanner;
import java.util.Random;

public class Baseball {
    public static void main(String[] args) throws Exception {

        // 랜덤으로 정답 만들기
        Random rand = new Random();

        int[] ans = {0, 0, 0};
        for (int i = 0; i < 3; i++){
            boolean isoverlap = true;
            while (isoverlap) {
                isoverlap = false;
                int num = rand.nextInt(10);
                for (int j = 0; j < i; j++){
                    if (num == ans[j] || num == 0){
                        isoverlap = true;
                    }
                }
                if (!isoverlap) {
                    ans[i] = num;
                }
            }
        }

        // 개발의 편의성을 위해 정답 출력
        int ans_num = ans[0] * 100 + ans[1] * 10 + ans[2];
        System.out.println(ans[0] + "" + ans[1] + "" + ans[2]);

        // 정답일 때 게임을 중단하기 위한 변수와 시도 횟
        boolean iscorrect = false;
        int cnt = 0;

        System.out.println("숫자야구게임을 시작합니다.");
        while(!iscorrect) {
            cnt++;
            System.out.println(cnt + " 번째 기회입니다.");

            Scanner sc = new Scanner(System.in);

            // 시도해볼 중복없는 수 만들기
            boolean isoverlap = true;
            int strike = 0;
            int ball = 0;
            int[] try_arr = new int[3];
            int try_ans = 0;

            while (isoverlap) {
                try_ans = sc.nextInt();
                try_arr[0] = (try_ans - try_ans % 100) / 100;
                try_arr[1] = (try_ans % 100 - try_ans % 100 % 10) / 10;
                try_arr[2] = try_ans % 10;
                if (try_arr[0] == try_arr[1] || try_arr[0] == try_arr[2] || try_arr[1] == try_arr[2]) {
                    isoverlap = true;
                } else {
                    isoverlap = false;
                }

                if (isoverlap) {
                    System.out.println("중복된 숫자가 존재합니다. 다시 입력해주세요.");
                }
            }

            if (try_ans == ans_num) {
                iscorrect = true;
            } else {
                System.out.println(try_ans + "를 입력하셨습니다.");

                for (int i = 0; i < 3; i++){
                    for (int j = 0; j < 3; j++){
                        if (try_arr[i] == ans[j]){
                            if (i == j) {
                                strike++;
                            } else {
                                ball++;
                            }
                        }
                    }
                }
                System.out.println(strike + "S" + ball + "B 입니다.");
                System.out.println("");
            }
        }
        System.out.println("정답은 " + ans_num + " 이었습니다!");
        System.out.println(cnt + "번 만에 정답을 맞추셨습니다!");
    }
}

첨삭1

import java.util.Scanner;
import java.util.Random;

public class Baseball {
    public static void main(String[] args) throws Exception {

        // 랜덤으로 정답 만들기
        Random rand = new Random();

        int[] ans = {0, 0, 0};
        for (int i = 0; i < 3; i++){
            boolean isoverlap = true;
            while (isoverlap) {
                boolean fail = false;
                int num = rand.nextInt(10);
                for (int j = 0; j < i; j++){
                    if (num == ans[j] || num == 0){
                        fail = true;
                        break;
                    }
                }
                if (!fail) {
                    ans[i] = num;
                    isoverlap = false;
                }
            }
        }

        // 개발의 편의성을 위해 정답 출력
        int ans_num = ans[0] * 100 + ans[1] * 10 + ans[2];
        System.out.println(ans[0] + "" + ans[1] + "" + ans[2]);

        // 정답일 때 게임을 중단하기 위한 변수와 시도 횟
        boolean iscorrect = false;
        int cnt = 0;

        System.out.println("숫자야구게임을 시작합니다.");
        while(!iscorrect) {
            cnt++;
            System.out.println(cnt + " 번째 기회입니다.");

            Scanner sc = new Scanner(System.in);

            // 시도해볼 중복없는 수 만들기
            boolean isoverlap = true;
            int strike = 0;
            int ball = 0;
            int[] try_arr = new int[3];
            int try_ans = 0;

            while (isoverlap) {
                try_ans = sc.nextInt();
                try_arr[0] = (try_ans - try_ans % 100) / 100;
                try_arr[1] = (try_ans % 100 - try_ans % 100 % 10) / 10;
                try_arr[2] = try_ans % 10;

                if (try_arr[0] == 0 || try_arr[1] == 0 || try_arr[2] == 0) {
                    System.out.println("0이 포함된 수 입니다. 다시 입력해주세요.");
                } else if (!(try_arr[0] == try_arr[1] || try_arr[0] == try_arr[2] || try_arr[1] == try_arr[2])) {
                    isoverlap = false;
                } else {
                    System.out.println("중복된 숫자가 존재합니다. 다시 입력해주세요.");
                }
            }

            if (try_ans == ans_num) {
                iscorrect = true;
            } else {
                System.out.println(try_ans + "를 입력하셨습니다.");

                for (int i = 0; i < 3; i++){
                    for (int j = 0; j < 3; j++){
                        if (try_arr[i] == ans[j]){
                            if (i == j) {
                                strike++;
                            } else {
                                ball++;
                            }
                        }
                    }
                }
                System.out.println(strike + "S" + ball + "B 입니다.");
                System.out.println("");
            }
        }
        System.out.println("정답은 " + ans_num + " 이었습니다!");
        System.out.println(cnt + "번 만에 정답을 맞추셨습니다!");
    }
}

첨삭2

2020.1.27

내 풀이 1:

field_original = [list(map(int, input().split())) for _ in range(10)]
result = 26

def pasting(i, j, count, field, use):
    global result
    try:
        if i == 9 and j == 9:
            if field[i][j] == 1:
                count += 1
            if result > count:
                result = count
            return

        if count > result:
            return


        if field[i][j] == 0:
            if j != 9:
                pasting(i, j + 1, count, field, use)
            elif i != 9:
                pasting(i + 1, 0, count, field, use)

        else:
            TF1 = False
            TF2 = False
            TF3 = False
            TF4 = False
            if max(i, j) <= 8:
                TF1 = True
                for _ in range(1):
                    if field[i+_][j+1] == 0:
                        TF1 = False
                        break
                for _ in range(2):
                    if field[i+1][j+_] == 0:
                        TF1 = False
                        break

            if TF1 and max(i, j) <= 7:
                TF2 = True
                for _ in range(2):
                    if field[i + _][j + 2] == 0:
                        TF2 = False
                        break
                for _ in range(3):
                    if field[i + 2][j + _] == 0:
                        TF2 = False
                        break
            if TF2 and max(i, j) <= 6:
                TF3 = True
                for _ in range(3):
                    if field[i + _][j + 3] == 0:
                        TF3 = False
                        break
                for _ in range(4):
                    if field[i + 3][j + _] == 0:
                        TF3 = False
                        break
            if TF3 and max(i, j) <= 5:
                TF4 = True
                for _ in range(4):
                    if field[i + _][j + 4] == 0:
                        TF4 = False
                        break
                for _ in range(5):
                    if field[i + 4][j + _] == 0:
                        TF4 = False
                        break


            new_use = use[:]
            if TF4 and new_use[4] <= 4:
                new_field = [line[:] for line in field]
                for _ in range(5):
                    for __ in range(5):
                        new_field[i+_][j+__] = 0
                new_use[4] += 1
                pasting(i, j + 1, count + 1, new_field, new_use)
                new_use[4] -= 1

            if TF3 and new_use[3] <= 4:
                new_field = [line[:] for line in field]
                for _ in range(4):
                    for __ in range(4):
                        new_field[i+_][j+__] = 0
                new_use[3] += 1
                pasting(i, j + 1, count + 1, new_field, new_use)
                new_use[3] -= 1

            if TF2 and new_use[2] <= 4:
                new_field = [line[:] for line in field]
                for _ in range(3):
                    for __ in range(3):
                        new_field[i+_][j+__] = 0
                new_use[2] += 1
                pasting(i, j + 1, count + 1, new_field, new_use)
                new_use[2] -= 1

            if TF1 and new_use[1] <= 4:
                new_field = [line[:] for line in field]
                for _ in range(2):
                    for __ in range(2):
                        new_field[i+_][j+__] = 0
                new_use[1] += 1
                pasting(i, j + 1, count+1, new_field, new_use)
                new_use[1] -= 1


            if new_use[0] <= 4:
                new_field = [line[:] for line in field]
                new_field[i][j] = 0
                new_use[0] += 1
                if j != 9:
                    pasting(i, j + 1, count + 1, new_field, new_use)
                elif i != 9:
                    pasting(i + 1, 0, count + 1, new_field, new_use)
                new_use[0] -= 1


    except:
        return


pasting(0, 0, 0, field_original, [0,0,0,0,0])
if result == 26:
    print("-1")
else:
    print(result)

Python3, 샘플은 맞았으나 오답

내 풀이 2:

field_original = [list(map(int, input().split())) for _ in range(10)]
result = 26

def pasting(i, j, count, field, use):
    global result
    if i == 9 and j == 9:
        if field[i][j] == 1:
            count += 1
            if use[0] == 5:
                return
        if result > count:
            result = count
        return

    if count == result:
        return


    if field[i][j] == 0:
        if j != 9:
            pasting(i, j + 1, count, field, use)
        elif i != 9:
            pasting(i + 1, 0, count, field, use)

    else:
        TF1 = False
        TF2 = False
        TF3 = False
        TF4 = False

        if max(i, j) <= 8:
            TF1 = True
            for _ in range(1):
                if field[i+_][j+1] == 0:
                    TF1 = False
                    break
            for _ in range(2):
                if field[i+1][j+_] == 0:
                    TF1 = False
                    break
        if TF1 and max(i, j) <= 7:
            TF2 = True
            for _ in range(2):
                if field[i + _][j + 2] == 0:
                    TF2 = False
                    break
            for _ in range(3):
                if field[i + 2][j + _] == 0:
                    TF2 = False
                    break
        if TF2 and max(i, j) <= 6:
            TF3 = True
            for _ in range(3):
                if field[i + _][j + 3] == 0:
                    TF3 = False
                    break
            for _ in range(4):
                if field[i + 3][j + _] == 0:
                    TF3 = False
                    break
        if TF3 and max(i, j) <= 5:
            TF4 = True
            for _ in range(4):
                if field[i + _][j + 4] == 0:
                    TF4 = False
                    break
            for _ in range(5):
                if field[i + 4][j + _] == 0:
                    TF4 = False
                    break


        new_use = use[:]
        if TF4 and new_use[4] <= 4:
            new_field = [line[:] for line in field]
            for _ in range(5):
                for __ in range(5):
                    new_field[i+_][j+__] = 0
            new_use[4] += 1
            pasting(i, j + 1, count + 1, new_field, new_use)
            new_use[4] -= 1

        if TF3 and new_use[3] <= 4:
            new_field = [line[:] for line in field]
            for _ in range(4):
                for __ in range(4):
                    new_field[i+_][j+__] = 0
            new_use[3] += 1
            pasting(i, j + 1, count + 1, new_field, new_use)
            new_use[3] -= 1

        if TF2 and new_use[2] <= 4:
            new_field = [line[:] for line in field]
            for _ in range(3):
                for __ in range(3):
                    new_field[i+_][j+__] = 0
            new_use[2] += 1
            pasting(i, j + 1, count + 1, new_field, new_use)
            new_use[2] -= 1

        if TF1 and new_use[1] <= 4:
            new_field = [line[:] for line in field]
            for _ in range(2):
                for __ in range(2):
                    new_field[i+_][j+__] = 0
            new_use[1] += 1
            pasting(i, j + 1, count+1, new_field, new_use)
            new_use[1] -= 1

        if new_use[0] <= 4:
            new_field = [line[:] for line in field]
            new_field[i][j] = 0
            new_use[0] += 1
            if j != 9:
                pasting(i, j + 1, count + 1, new_field, new_use)
            elif i != 9:
                pasting(i + 1, 0, count + 1, new_field, new_use)
            new_use[0] -= 1


pasting(0, 0, 0, field_original, [0,0,0,0,0])
if result == 26:
    print("-1")
else:
    print(result)

Python3, 1424ms (9, 9)를 마지막으로 확인할 때 색종이를 붙여야 하는 구역이면 count만 1 올려주고 답을 출력했었는데 이때 이미 1*1짜리 색종이를 5장 사용한 상태라면 조건에 부합하기 때문에 이 과정을 생략하여 오답이 나왔었다.

2020.1.27

내 풀이 1:

N, M, D = map(int, input().split())
field_original = []
for _ in range(N):
    field_original.append(list(map(int, input().split())))


result = 0


def defense(field, hunt, index, archer1, archer2, archer3):
    global result
    if index == N:
        if result < hunt:
            result = hunt

        return


    D1 = D+1
    D2 = D+1
    D3 = D+1
    cnt_hunt = 0
    for i in range(N):
        for j in range(M):
            if field[i][j] == 0:
                continue

            if abs(i-N) + abs(j-archer1) < D1:
                D1 = abs(i-N) + abs(j-archer1)
                target1 = [i, j]

            if abs(i-N) + abs(j-archer2) < D2:
                D2 = abs(i-N) + abs(j-archer2)
                target2 = [i, j]

            if abs(i-N) + abs(j-archer3) < D3:
                D3 = abs(i-N) + abs(j-archer3)
                target3 = [i, j]

    if D1 < D+1:
        field[target1[0]][target1[1]] = 0
        cnt_hunt += 1

    if D2 < D+1:
        if field[target2[0]][target2[1]] == 1:
            field[target2[0]][target2[1]] = 0
            cnt_hunt += 1

    if D3 < D+1:
        if field[target3[0]][target3[1]] == 1:
            field[target3[0]][target3[1]] = 0
            cnt_hunt += 1

    for i in range(N-2, -1, -1):
        for j in range(M):
            field[i+1][j] = field[i][j]


    defense(field, hunt+cnt_hunt, index+1, archer1, archer2, archer3)


def archer_position(position, index):
    if index == 3:
        defense(field_original, 0, 0, position[0], position[1], position[2])
        return

    if index == 0:
        for _ in range(M-2):
            position.append(_)
            archer_position(position, index+1)
            del position[-1]
        return

    for __ in range(M):
        if max(position) >= __:
            continue
        position.append(__)
        archer_position(position, index+1)
        del position[-1]

archer_position([], 0)
print(result)

Python3, 오답 재귀 함수가 실행이 되지 않는다고 생각했는데 중간중간 print를 넣어가며 확인해본 결과 재귀는 실행되나 아처 3명이 배치된 후 defense()가 실행된 결과에 hunt가 계속해서 0인 것을 확인했다. 재귀 함수에 list가 들어가는 경우 이 리스트에 변화를 일으켜서 다시 재귀에 넣는 경우 shallow copy가 일어나 결과가 엉망이 돼버렸다.

내 풀이 2:

N, M, D = map(int, input().split())
field_original = []
for _ in range(N):
    field_original.append(list(map(int, input().split())))


result = 0


def defense(field, hunt, index, archer1, archer2, archer3):
    global result
    if index == N:
        if result < hunt:
            result = hunt
        return

    D1 = D+1
    D2 = D+1
    D3 = D+1
    cnt_hunt = 0
    new_field = [[0] * M for _ in range(N)]
    for i in range(N):
        for j in range(M):
            new_field[i][j] = field[i][j]
    for j in range(M):
        for i in range(N):
            if new_field[i][j] == 0:
                continue

            if abs(i-N) + abs(j-archer1) < D1:
                D1 = abs(i-N) + abs(j-archer1)
                target1 = [i, j]

            if abs(i-N) + abs(j-archer2) < D2:
                D2 = abs(i-N) + abs(j-archer2)
                target2 = [i, j]

            if abs(i-N) + abs(j-archer3) < D3:
                D3 = abs(i-N) + abs(j-archer3)
                target3 = [i, j]


    if D1 < D+1:
        new_field[target1[0]][target1[1]] = 0
        cnt_hunt += 1

    if D2 < D+1:
        if new_field[target2[0]][target2[1]] == 1:
            new_field[target2[0]][target2[1]] = 0
            cnt_hunt += 1

    if D3 < D+1:
        if new_field[target3[0]][target3[1]] == 1:
            new_field[target3[0]][target3[1]] = 0
            cnt_hunt += 1

    for i in range(N-2, -1, -1):
        for j in range(M):
            new_field[i+1][j] = new_field[i][j]

    for j in range(M):
        new_field[0][j] = 0

    defense(new_field, hunt+cnt_hunt, index+1, archer1, archer2, archer3)


def archer_position(position, idx):
    if idx == 3:
        defense(field_original, 0, 0, position[0], position[1], position[2])
        return

    if idx == 0:
        for _ in range(M-2):
            position.append(_)
            archer_position(position, idx+1)
            del position[-1]
        return

    for __ in range(M):
        if max(position) >= __:
            continue

        position.append(__)
        archer_position(position, idx+1)
        del position[-1]

archer_position([], 0)
print(result)

Python3, 764ms shallow copy에서 발생하는 문제를 해결하고자 defense 함수 자체에서 new_field라는 리스트를 새로 만들어 사용하였다. 또한 target 탐색 순서를 세로로 우선적으로 하여 문제에서 요구하던 조건인 <같은 거리의 적의 경우 가장 왼편의 적을 공격한다>를 새로운 변수 혹은 if문 없이 해결할 수 있었다.

jinhot님의 풀이:

N, M, D = map(int, input().split())

board = []

for _ in range(N):
    board.append(list(map(int, input().split())))

def shoot(y, position, s_board):
    for d in range(1, D+1):
        for left in range(d, -1, -1): # left 부터 파악
            height = d - left
            if height > 0 and 0 <= y - height < N and 0 <= position - left < M and s_board[y - height][position - left] == 1:
                return (y - height, position - left)
        for right in range(1, d+1, 1): # left 부터 파악
            height = d - right
            if height > 0 and 0 <= y - height < N and 0 <= position + right < M and s_board[y - height][position + right] == 1:
                return (y - height, position + right)

    return None

def simulation(positions):
    s_board = [line[:] for line in board]
    killed_amount = 0
    for y in range(N, 0, -1):
        killed = []
        for position in positions:
            killed_enemy = shoot(y, position, s_board)
            if killed_enemy is not None:
                killed.append(killed_enemy)
        for killed_enemy in killed:
            if s_board[killed_enemy[0]][killed_enemy[1]] == 1:
                s_board[killed_enemy[0]][killed_enemy[1]] = 0
                killed_amount += 1
    return killed_amount

max_v = 0
for i in range(M):
    for j in range(i + 1, M):
        for k in range(j + 1, M):
            max_v = max(max_v, simulation((i, j, k)))

print(max_v)

Python3, 112ms 먼저 아처의 포지션을 재귀 함수가 아닌 3중 for문을 이용하여 가독성도 좋고 코딩 시간, 길이는 물론 실행 시간도 짧게 걸린다. 또한 shoot 함수가 필요로 하는 변수를 줄인 것도 눈에 띈다. simulation 함수에서 튜플로 받은 아처의 포지션 원소에 대해 함수를 실행시킨다.

2020.1.26

내 풀이:

N = int(input())
expression = input()
answer = -2 ** 31

if N == 1:
    print(max(answer, int(expression)))
    exit()

symbol = ["+", "-", "*"]


def add_parenthesis(index, expression_list):
    global answer
    if index == N:
        for i, j in enumerate(expression_list):
            if len(j) == 3:
                expression_list[i] = str(eval(j))
        result = expression_list[0]
        for _ in range(1, len(expression_list), 2):
            result = eval(str(result)+expression_list[_]+expression_list[_+1])

        if answer < result:
            answer = result
        return


    expression_list.append(expression[index])
    add_parenthesis(index + 1, expression_list)
    del expression_list[-1]

    if expression_list[-1] in symbol and index + 3 <= N:
        expression_list.append(expression[index:index+3])
        add_parenthesis(index + 3, expression_list)
        del expression_list[-1]


add_parenthesis(1, [expression[0]])
print(answer)

Python3, 60ms 이번 문제에서는 내장함수를 공부할 때 개인적으로 인상깊었던 eval() 함수를 사용했다. 괄호를 추가했다는 것을 구분하는 방법으로 리스트에 괄호로 싸인 (숫자+기호+숫자)를 한 번에 추가하는 것으로 처리하였다. 코딩을 하는 과정에서 에러가 많이 발생해 조금 해맸는데 그 이유는 eval() 함수로 출력되는 수의 타입이 int라는 사실을 몰랐기 때문이다. 만약 이전에 eval()을 사용해보았다면 코딩 과정에서 eval()의 결과값마다 str 처리를 해주어 문제를 빠르게 풀 수 있었을 것 같다.

2020.1.23

내 풀이 1:

N = int(input())
people = list(map(int, input().split()))
people.insert(0, 0)
connection = [[]]
answer = 10000
for _ in range(N):
    a = list(map(int, input().split()))
    del a[0]
    connection.append(a)



def making_team(index, A, B):
    global answer
    if index == N:
        if B == []:
            return

        for i in A:
            TF = False
            for j in A:
                if j in connection[i]:
                    TF = True
                    break
                else:
                    pass
            if not TF:
                return

        for i in B:
            TF = False
            for j in B:
                if j in connection[i]:
                    TF = True
                    break
                else:
                    pass
            if not TF:
                return

        sumA = 0
        sumB = 0

        for i in A:
            sumA += people[i]
        for i in B:
            sumB += people[i]
        result = abs(sumA - sumB)

        if answer > result:
            answer = result

        return


    A_new = A[:]
    B_new = B[:]
    A_new.append(index+1)
    B_new.append(index+1)
    making_team(index+1, A_new, B)
    making_team(index+1, A, B_new)


making_team(1, [1], [])
if answer == 10000:
    print("-1")
    exit()
print(answer)

Python3, 오답 샘플은 모두 통과하였으나 제출했을 때 오답 판정을 받았다.

내 풀이 2:

N = int(input())
people = list(map(int, input().split()))
people.insert(0, 0)
connection = [[]]
answer = 1000
for _ in range(N):
    a = list(map(int, input().split()))
    del a[0]
    connection.append(a)


def checking(team):
    check_list = [team[0]]
    for _ in range(len(team)-1):
        for i in check_list:
            for j in connection[i]:
                if j not in check_list and j in team:
                    check_list.append(j)
    if len(check_list) == len(team):
        return True
    else:
        return False


def making_team(index, A, B):
    global answer
    if index == N:
        if B == []:
            return

        if not checking(A):
            return

        if not checking(B):
            return

        sumA = 0
        sumB = 0

        for i in A:
            sumA += people[i]
        for i in B:
            sumB += people[i]
        result = abs(sumA - sumB)

        if answer > result:
            answer = result

        return

    A_new = A[:]
    B_new = B[:]
    A_new.append(index+1)
    B_new.append(index+1)
    making_team(index+1, A_new, B)
    making_team(index+1, A, B_new)


making_team(1, [1], [])
if answer == 1000:
    print("-1")
    exit()
print(answer)

Python3, 80ms 선거구를 나누는 과정까진 오류가 없었으나 선거구를 정하고 그 선거구에 어느 한 구역도 빠짐없이 연결돼있는가를 확인하는 알고리즘이 틀렸었다. 처음 작성한 코드에서는 어느 구역이든 한 구역이라도 연결된 곳이 있다면 문제가 없다는 식으로 코딩을 했으나 4개의 구역으로 이루어진 선거구가 2/2로 쪼개진다면 조건을 만족하지 않음에도 조건을 통과하는 문제가 발생하기에 이를 수정하였다. 지금까지는 종이에 따로 문제에 대해 미리 적어보고 코딩을 시작하는 것이 아니라 문제를 읽는 즉시 코딩에 들어갔는데 이 때문에 문제 분석에 들어가는 시간이 배 이상으로 들어가는 것 같다. 시험 준비를 목표로 한다면 한 문제 한 문제 풀 때마다 미리 종이에 문제에 대한 조건 등을 분석하여 적어놓고 이를 토대로 코딩하는 연습이 필요할 것이다.

2020.1.23

내 풀이 1:

N, M, K = map(int,input().split())
origin_arr = [list(map(int, input().split())) for _ in range(N)]
new_arr = [[0] * M for _ in range(N)]
rcs = []
answer = []

def rotation(r, c, s, arr):
    global new_arr
    for i in range(N):
        for j in range(M):
            new_arr[i][j] = arr[i][j]

    for shell in range(1, s+1):
        for x in range(2*shell):
            new_arr[r-shell-1+x][c-shell-1] = arr[r-shell+x][c-shell-1]

        for x in range(2*shell):
            new_arr[r+shell-1][c-shell-1+x] = arr[r+shell-1][c-shell+x]

        for x in range(2*shell):
            new_arr[r+shell-1-x][c+shell-1] = arr[r+shell-2-x][c+shell-1]

        for x in range(2*shell):
            new_arr[r-shell-1][c+shell-1-x] = arr[r-shell-1][c+shell-2-x]


def sequence(index, K, table):
    global answer
    if index == K:
        r = rcs[table[0]][0]
        c = rcs[table[0]][1]
        s = rcs[table[0]][2]
        rotation(r, c, s, origin_arr)

        for __ in range(1, K):
            r = rcs[table[__]][0]
            c = rcs[table[__]][1]
            s = rcs[table[__]][2]
            rotation(r, c, s, new_arr)

        result = sum(new_arr[0])
        for idx in range(1, N):
            if result > sum(new_arr[idx]):
                result = sum(new_arr[idx])

        answer.append(result)
        return

    for _ in range(K):
        if _ in table:
            continue
        table.append(_)
        sequence(index+1, K, table)
        table.remove(_)


for _ in range(K):
    r, c, s = map(int, input().split())
    rcs.append([r, c, s])

sequence(0, K, [])

print(min(answer))

Python3, 오답 샘플이 1개밖에 없는데 샘플은 정답이 나와서 아직 고민 중...

내 풀이 2:

N, M, K = map(int,input().split())
arr = [list(map(int, input().split())) for _ in range(N)]
new_arr = [[0] * M for _ in range(N)]
rcs = []
answer = []
for i in range(N):
    for j in range(M):
        new_arr[i][j] = arr[i][j]


def rotation(r, c, s, arr):
    global new_arr
    for i in range(N):
        for j in range(M):
            new_arr[i][j] = arr[i][j]

    for shell in range(1, s+1):
        for x in range(2*shell):
            new_arr[r-1-shell][c-1-shell+1+x] = arr[r-1-shell][c-1-shell+x]

        for x in range(2*shell):
            new_arr[r-1-shell+1+x][c-1+shell] = arr[r-1-shell+x][c-1+shell]

        for x in range(2*shell):
            new_arr[r-1+shell][c-1+shell-1-x] = arr[r-1+shell][c-1+shell-x]

        for x in range(2*shell):
            new_arr[r-1+shell-1-x][c-1-shell] = arr[r-1+shell-x][c-1-shell]


def sequence(index, K, table):
    global answer
    if index == K:
        r = rcs[table[0]][0]
        c = rcs[table[0]][1]
        s = rcs[table[0]][2]
        rotation(r, c, s, arr)

        for __ in range(1, K):
            r = rcs[table[__]][0]
            c = rcs[table[__]][1]
            s = rcs[table[__]][2]
            rotation(r, c, s, new_arr)

        result = sum(new_arr[0])
        for idx in range(1, N):
            if result > sum(new_arr[idx]):
                result = sum(new_arr[idx])

        answer.append(result)
        return

    for _ in range(K):
        if _ in table:
            continue
        table.append(_)
        sequence(index+1, K, table)
        table.remove(_)


for _ in range(K):
    r, c, s = map(int, input().split())
    rcs.append([r, c, s])

sequence(0, K, [])

print(min(answer))

Python3, 샘플 오답 잘못 작성했던 rotation함수를 내가 생각했던, 그리고 가독성이 좋게 수정하였다. 그러나 line 37의 rotation은 잘 돌아가는데 line 43의 rotation은 함수 내 new_arr와 arr가 메모리를 공유(shallow copy)되면서 원하는 결과를 출력하지 않았다.

내 풀이 3:

N, M, K = map(int,input().split())
arr = [list(map(int, input().split())) for _ in range(N)]
next_arr = [[0] * M for _ in range(N)]
rcs = []
answer = []
for i in range(N):
    for j in range(M):
        next_arr[i][j] = arr[i][j]


def rotation(r, c, s, arr):
    new_arr = [[0] * M for _ in range(N)]
    for i in range(N):
        for j in range(M):
            new_arr[i][j] = arr[i][j]

    for shell in range(1, s+1):
        for x in range(2*shell):
            new_arr[r-1-shell][c-1-shell+1+x] = arr[r-1-shell][c-1-shell+x]

        for x in range(2*shell):
            new_arr[r-1-shell+1+x][c-1+shell] = arr[r-1-shell+x][c-1+shell]

        for x in range(2*shell):
            new_arr[r-1+shell][c-1+shell-1-x] = arr[r-1+shell][c-1+shell-x]

        for x in range(2*shell):
            new_arr[r-1+shell-1-x][c-1-shell] = arr[r-1+shell-x][c-1-shell]

    return new_arr


def sequence(index, K, table):
    global answer
    if index == K:
        r = rcs[table[0]][0]
        c = rcs[table[0]][1]
        s = rcs[table[0]][2]
        next_arr = rotation(r, c, s, arr)

        for __ in range(1, K):
            r = rcs[table[__]][0]
            c = rcs[table[__]][1]
            s = rcs[table[__]][2]
            next_arr = rotation(r, c, s, next_arr)

        result = sum(next_arr[0])
        for idx in range(1, N):
            if result > sum(next_arr[idx]):
                result = sum(next_arr[idx])

        answer.append(result)
        return

    for _ in range(K):
        if _ in table:
            continue
        table.append(_)
        sequence(index+1, K, table)
        table.remove(_)


for _ in range(K):
    r, c, s = map(int, input().split())
    rcs.append([r, c, s])


sequence(0, K, [])

print(min(answer))

Python3, 2100ms 전역 변수 new_arr를 제거하고 next_arr라는 변수를 새로 만들어서 메모리 공유하는 것을 방지하였다.

2020.11.30

내 풀이:

# 2020.11.30
# 13:20 ~ 13:56

N, M, K = map(int, input().split())
arr = []
for _ in range(N):
    row = list(map(int, input().split()))
    arr.append(row)

rotations = []
for _ in range(K):
    r, c, s = map(int, input().split())
    rotations.append((r-1, c-1, s))

visited = [False] * K
answer = 10 ** 9


def action(r, c, s):
    for d in range(1, s + 1):
        save = arr[r - d][c - d]
        for i in range(r - d, r + d):
            arr[i][c - d] = arr[i + 1][c - d]
        for j in range(c - d, c + d):
            arr[r + d][j] = arr[r + d][j + 1]
        for i in range(r + d, r - d, -1):
            arr[i][c + d] = arr[i - 1][c + d]
        for j in range(c + d, c - d, -1):
            arr[r - d][j] = arr[r - d][j - 1]
        arr[r - d][c - d + 1] = save


def backup(r, c, s):
    for d in range(1, s + 1):
        save = arr[r - d][c - d]
        for j in range(c - d, c + d):
            arr[r - d][j] = arr[r - d][j + 1]
        for i in range(r - d, r + d):
            arr[i][c + d] = arr[i + 1][c + d]
        for j in range(c + d, c - d, -1):
            arr[r + d][j] = arr[r + d][j - 1]
        for i in range(r + d, r - d, -1):
            arr[i][c - d] = arr[i - 1][c - d]
        arr[r - d + 1][c - d] = save


def rotation():
    global answer
    if False not in visited:
        for i in range(N):
            answer = min(answer, sum(arr[i]))
        return

    for idx in range(K):
        if not visited[idx]:
            r, c, s = rotations[idx]
            visited[idx] = True
            action(r, c, s)

            rotation()

            visited[idx] = False
            backup(r, c, s)

rotation()
print(answer)

Python3, 740ms 재귀를 이용한 DFS 백트래킹으로 문제를 해결하였다. 재귀 깊이가 최대 6이기 때문에 굳이 스택 형태로 구현할 필요가 없었다. 회전시키는 action함수와 회전했던 부분을 복구시키기 위한 backup함수를 따로 구현하였다. Deep Copy를 이용하는 대신 복구시키는 함수를 따로 구현하였기 때문에 이전보다 실행시간을 단축할 수 있었다.

2020.1.22

내 풀이:

def move(location, style):
    if style == 0:
        return location
    elif style == 1:
        location[0] -= 1
        return location
    elif style == 2:
        location[1] += 1
        return location
    elif style == 3:
        location[0] += 1
        return location
    elif style == 4:
        location[1] -= 1
        return location


def score(location):
    score = [0] * A
    for tt in range(A):
        if abs(location[0] - AP[tt][1]+1) + abs(location[1] - AP[tt][0]+1) <= AP[tt][2]:
            score[tt] = AP[tt][3]
    return score


def cal(score1, score2):
    result = 0
    if A ==1:
        return max(score1[0], score2[0])
    for i in range(A):
        for j in range(A):
            if i == j:
                pass
            else:
                if score1[i] + score2[j] > result:
                    result = score1[i] + score2[j]
    return result


T = int(input())
for _ in range(T):
    M, A = map(int, input().split())
    move1 = list(map(int, input().split()))
    move2 = list(map(int, input().split()))
    AP = []
    for t in range(A):
        AP.append(list(map(int, input().split())))
    user1 = [0,0]
    user2 = [9,9]
    result = 0
    result += cal(score(user1),score(user2))

    for __ in range(M):
        user1 = move(user1, move1[__])
        user2 = move(user2, move2[__])
        result += cal(score(user1), score(user2))
    print("#%d %d" % (_ + 1, result))

Python, 319ms 문제를 제대로 안 읽고 풀다가 BC (Battery Charger)가 1~8개라는 조건을 뒤늦게 알고 코드를 고치느라 고생했다. 문제를 꼼꼼히 읽자.

2020년 11월 28일 저녁 6시부터 3시간동안 진행된 알고리즘 프로그래밍 경시대회에 참여하였다.

A 내 풀이:

N = int(input())
lst = list(map(int, input().split()))
cnt = 0
last_num = lst[0]

for idx, num in enumerate(lst):
    if idx % 2 == num % 2:
        print("NO")
        break
else:
    print("YES")

B 내 풀이:

S = input()
num_of_zero = 0
for c in S:
    if c == '0':
        num_of_zero += 1
num_of_one = (len(S) - num_of_zero) // 2
num_of_zero //= 2

ans = ''
for c in S:
    if c == '0':
        if num_of_zero > 0:
            num_of_zero -= 1
            ans += '0'
    elif c == '1':
        if not num_of_one:
            ans += '1'
        else:
            num_of_one -= 1

print(ans)

C 내 풀이:

N, K = map(int, input().split())
lst = list(map(int, input().split()))
data = []
for idx, cnt in enumerate(lst):
    data.append([cnt, str(idx + 1)])

data.sort(key=lambda x: -x[0])
if data[0][0] > N // 2 + N % 2:
    print("-1")
else:
    lst = []
    for cnt, num in data:
        lst += [num] * cnt
    end = len(lst)
    ans = []
    for i in range(end):
        if not i % 2:
            ans.append(lst[i // 2])
        else:
            ans.append(lst[end - 1 - i // 2])
    print(' '.join(ans))

D 내 풀이:

N = int(input())
data = list(map(int, input().split()))

ans = 0
num = 1

for n in data:
    num *= n
    n %= (10 ** 9 + 7)
    ans += num
    num += 1

print(ans % (10 ** 9 + 7))

E 내 풀이:

from collections import deque

N, M, A, B = map(int, input().split())
road = {}
magic = []
row = []
for i in range(M):
    U, V, T = map(int, input().split())
    if U in road:
        road[U].add((V, i))
    else:
        road[U] = set()
        road[U].add((V, i))
    if V in road:
        road[V].add((U, i))
    else:
        road[V] = set()
        road[V].add((U, i))
    row.append(T)
magic.append(row)

K = int(input())
for _ in range(K):
    row = list(map(int, input().split()))
    magic.append(row)

res = [[10**13] * (K+1) for _ in range(N+1)]
q = deque()
q.append((A, 0))
res[A][0] = 0

while q:
    s, row = q.popleft()
    for tu in road[s]:
        e, i = tu
        new = res[s][row] + magic[row][i]
        if res[e][row] > new:
            res[e][row] = new
            q.append((e, row))
        if row < K:
            new = res[s][row] + magic[row + 1][i]
            if res[e][row + 1] > new:
                res[e][row + 1] = new
                q.append((e, row + 1))

print(min(res[B]))

2020.1.18

내 풀이 1:

N = int(input())
result = 0

def move(y,x,style):
    global result
    if y == N-1 and x == N-1:
        result += 1
        return

    if style == 1:
        if x == N-1:
            return

        if table[y][x+1] == 0:
            move(y,x+1,1)
            if table[y+1][x+1] == 0 and table[y+1][x] == 0:
                move(y+1,x+1,2)
            return

    elif style == 2:
        if x == N-1:
            for check in range(y, N):
                if table[check][x] == 1:
                    return
            result += 1
            return


        elif y == N-1:
            for check in range(x, N):
                if table[y][check] == 1:
                    return
            result += 1
            return

        if table[y][x+1] == 0:
            move(y,x+1,1)
            if table[y+1][x+1] == 0 and table[y+1][x] == 0:
                move(y+1,x+1,2)
                move(y+1,x,3)
                return
            elif table[y+1][x] == 0:
                move(y+1, x, 3)
                return

        elif table[y+1][x] == 0:
            move(y+1,x,3)
            return

    elif style == 3:
        if y == N-1:
            return
        if table[y+1][x] == 0:
            move(y+1,x,3)
            if table[y+1][x+1] == 0 and table[y][x+1] == 0:
                move(y+1,x+1,2)
        return


table = []
for i in range(N):
    table_mini = list(map(int, input().split()))
    table.append(table_mini)

move(0,1,1)
print(result)

932ms, pypy style 1을 오른쪽, style 2를 대각선, style 3을 아래쪽 방향으로 구분하였다. 이번 코딩에서 발생한 문제로는 첫 번째로 벽에 도착했을 때 처리하는 방식을 if문으로 해결하다 보니 이동하는 모든 경우에 있어서 벽인가를 체크하여 시간이 지연된다. for문 안에 if문이 많을 경우 시간이 기하급수적으로 오래 걸리기 때문에 가능하면 for문 밖에서 해결하거나 아예 다른 방식으로 접근하는 습관을 들여야 한다. 또한 if문에서 첫 조건만을 통과하고 그 이후로 모든 조건을 통과하지 못했을 때의 상황은 return과 같이 해석을 해야 했는데 그다음 elif를 실행시킬 것이라고 착각하여 오랜 시간을 낭비하였다.

내 풀이 2:

N = int(input())
result = 0

def move(y,x,style):
    global result
    if y == N-1 and x == N-1:
        result += 1
        return

    if style == 1:
        if x == N-1:
            return

        if table[y][x+1] == 0:
            move(y,x+1,1)
            if table[y+1][x+1] == 0 and table[y+1][x] == 0:
                move(y+1,x+1,2)
            return

    elif style == 2:
        if x == N-1:
            for check in range(y, N):
                if table[check][x] == 1:
                    return
            result += 1
            return


        elif y == N-1:
            for check in range(x, N):
                if table[y][check] == 1:
                    return
            result += 1
            return

        if table[y + 1][x + 1] == 0 and table[y + 1][x] == 0 and table[y][x + 1] == 0:
            move(y, x + 1, 1)
            move(y + 1, x + 1, 2)
            move(y + 1, x, 3)
            return

        if table[y][x+1] == 0:
            move(y, x + 1, 1)

        if table[y+1][x] == 0:
            move(y + 1, x, 3)


    elif style == 3:
        if y == N-1:
            return
        if table[y+1][x] == 0:
            move(y+1,x,3)
            if table[y+1][x+1] == 0 and table[y][x+1] == 0:
                move(y+1,x+1,2)
        return


table = []
for i in range(N):
    table_mini = list(map(int, input().split()))
    table.append(table_mini)

move(0,1,1)
print(result)

844ms, pypy style 2에서 if문을 정돈하였더니 시간이 약간 줄어들었다.

내 풀이 3:

N = int(input())
result = 0

def move(y,x,style):
    global result
    if y == N-1 and x == N-1:
        result += 1
        return

    if style == 1:
        if table[y][x+1] == 0:
            move(y,x+1,1)
            if table[y+1][x+1] == 0 and table[y+1][x] == 0:
                move(y+1,x+1,2)
            return

    elif style == 2:
        if table[y + 1][x + 1] == 0 and table[y + 1][x] == 0 and table[y][x + 1] == 0:
            move(y, x + 1, 1)
            move(y + 1, x + 1, 2)
            move(y + 1, x, 3)
            return

        if table[y][x+1] == 0:
            move(y, x + 1, 1)

        if table[y+1][x] == 0:
            move(y + 1, x, 3)


    elif style == 3:
        if table[y+1][x] == 0:
            move(y+1,x,3)
            if table[y+1][x+1] == 0 and table[y][x+1] == 0:
                move(y+1,x+1,2)
        return


table = []
for i in range(N):
    table_mini = list(map(int, input().split()))
    table_mini.append(1)
    table.append(table_mini)
table.append([1] * (N + 1))
move(0,1,1)
print(result)

1000ms, pypy 벽을 만났을 때 처리해주기 위한 별도의 if문들을 모두 없애고 바깥쪽에 1을 둘러싸서 알고리즘으로 해결하였다. 이렇게 하면 if문의 개수가 줄어들기 때문에 시간도 줄어들 것이라 기대했는데 오히려 늘어났다. 이 말은 즉, 벽에 도달한 경우에 바로 result를 1 올려주고 return 하는 대신 계속해서 재귀를 돌리게 되어 시간이 오래 걸렸다는 것을 말한다. 시간을 줄이기 위해서는 몇 개의 조건문을 추가하여 불필요한 재귀가 발생하는 것을 줄이는 게 오히려 시간 단축에 더 도움이 된다는 얘기이다.

jeonsewallse님 풀이:

# DP를 이용해서 풀이
N = int(input())

field = [input().split() + ['1'] for _ in range(N)]
field.append(['1'] * (N + 1))
wall = '1'
road = '0'
# 도착했을 때 방향을 고려하여 경우의 수 분리
arrive_right = [[0]*N for _ in range(N)]
arrive_down = [[0]*N for _ in range(N)]
arrive_cross = [[0]*N for _ in range(N)]

# 첫 줄의 경우의 수 갱신
for c in range(1, N):
    if field[0][c] == '0':
        arrive_right[0][c] = 1
    else:
        break

# 행 마다 경우의 수 갱신
for r in range(1, N):
    for c in range(1, N):
        if field[r][c] == road and field[r-1][c] == road and field[r][c-1] == road:
            # 대각선으로 도착할 수 있는 경우의 수 갱신
            arrive_cross[r][c] = arrive_right[r-1][c-1] + arrive_down[r-1][c-1] + arrive_cross[r-1][c-1]
        if field[r][c] == road:
            # 가로로 도착한 경우, 세로로 도착할 수 있는 경우의 수 갱신
            arrive_right[r][c] = arrive_right[r][c-1] + arrive_cross[r][c-1]
            arrive_down[r][c] = arrive_down[r-1][c] + arrive_cross[r-1][c]

ans = arrive_right[N-1][N-1] + arrive_down[N-1][N-1] + arrive_cross[N-1][N-1]

print(ans)

64ms, python3 Dynamic Programing(동적 계획법)을 이용한 풀이. 기존의 내 코딩과 이 코딩의 차이점은 어릴 때 많이 풀어보았던 길찾기 문제를 떠올리면 된다. 내 코드는 모든 경로를 직접 탐색해서 총 100가지가 나온다면 100개의 경로 그 이상을 탐색해야 하지만 길 찾기 문제를 몇 번의 덧셈으로 풀곤 하였는데 이 코드가 그러한 방식과 동일하다고 생각하면 된다. 이 풀이는 N이 20이라 할지라도 20*20 이라는 field 크기만큼의 계산만을 필요로 한다. 따라서 재귀를 이용한 풀이가 항상 능사는 아니라는 것을 명심해야 할 것이다.

2020.11.27

내 풀이 1:

# 2020.11.27
# 16:07 ~ 16:23

N = int(input())
field = []
for _ in range(N):
    row = list(map(int, input().split()))
    field.append(row)

stack = [(0, 1, 0)]
ry = (0, 1, 1)
rx = (1, 1, 0)


def check(y, x, dirc):
    for dy in range(ry[dirc] + 1):
        for dx in range(rx[dirc] + 1):
            ny = y + dy
            nx = x + dx
            if field[ny][nx]:
                return False
    return True


answer = 0
while stack:
    y, x, last_dirc = stack.pop()
    for dirc in range(3):
        if abs(dirc - last_dirc) <= 1:
            ny = y + ry[dirc]
            nx = x + rx[dirc]
            if 0 <= ny < N and 0 <= nx < N:
                if check(y, x, dirc):
                    if ny == N - 1 and nx == N - 1:
                        answer += 1
                    else:
                        stack.append((ny, nx, dirc))

print(answer)

시간초과, python3 최대 16*16이고 각 지점에서 3가지 방법이 존재한다고 할 때, 못해도 3³⁰가지 이상의 방법이 존재한다. 때문에 당연하게도 DFS를 이용한 방법은 사용해서는 안됐는데 구현 과정이 너무 명확하다보니 스택을 이용한 DFS방법을 이용하였고 시간초과가 났다. 이동 방법이 단 3가지 밖에 없기 때문에 좌표와 방향을 이용한 DP로 풀어야 한다.

내 풀이 2:

# 2020.11.27
# 16:07 ~ 16:37

N = int(input())
field = []
for _ in range(N):
    row = list(map(int, input().split()))
    field.append(row)

DP = [[[0, 0, 0] for _ in range(N)] for _ in range(N)]
DP[0][1][0] = 1
for i in range(N):
    for j in range(1, N):
        if not field[i][j]:
            if j > 0:
                DP[i][j][0] += DP[i][j-1][0] + DP[i][j-1][1]
                if i > 0:
                    if not field[i-1][j] and not field[i][j-1]:
                        DP[i][j][1] += sum(DP[i-1][j-1])
            if i > 0:
                DP[i][j][2] += DP[i-1][j][1] + DP[i-1][j][2]

answer = sum(DP[N-1][N-1])
print(answer)

76ms, python3 DP를 이용할 때, 분기를 최대한 깔끔하게 짜고 싶었는데, y와 x좌표에 분기를 걸어주다보니 생각보다는 지저분하게 코드가 작성된 것 같아서 아쉽다. 반복문이 돌면서 분기를 계속 지나야하기 때문에 비효율적이라는 느낌도 지울수가 없었다. 때문에 차라리 첫 줄만 따로 처리해주고 i>0, j>0 에 대해서만 코드를 진행시키는게 더 좋았을 것 같다. 해당 변경 내용은 위의 jeonsewallse님의 풀이를 참고하면 될 것 같다.