투투

문제 NxM의 맵에서 1은 벽이기 때문에 이동할 수 없고 0은 이동할 수 있다. (1, 1)에서 출발하여 (N, M)까지 이동을 할 때 최소로 이동하는 거리를 구한다. 이때 벽으로인해 이동할 수 없다면 최대 한 번은 벽을 부수고 이동할 수 없다. 벽을 부수고 이동했을 때도 도착지에 가지 못한다면 -1을 출력한다. 입력 첫째 줄에 1이상 1000이하의 N과 M을 입력한다. 출력 첫째 줄에 최소거리를 출력한다. 접근 처음에는 맵을 탐색하다가 벽이 보였을 때 벽을 제거하고 BFS를 하도록 했지만 시간초과가 났다. 그래서 여러번 시도를 해보고 다른 사람들의 풀이를 참고하였다. BFS를 할 때 3차원 배열로 방문표시와 이동거리를 표시를 한다. 마지막 축은 크기가 2인데 0은 벽을 부수고 이동한거리, 1은 벽을 부..

문제 스타트링크에 다니는 사람들이 모여서 축구를 한다. 모인 사람은 항상 짝수인 N명이 모였으며 스타트팀과 링크팀으로 나누려고 한다. 이때 i와 j가 팀이 되었을 때 능력치가 있는데 N명이 두 팀으로 나눴을 때 각각 팀의 능력치를 구하여 두 팀의 능력치 차이가 최소가 되도록 구하라. 입력 첫째 줄에 N이 주어진다. 둘째 줄부터 N개의 줄에 N개의 능력치가 주어진다. i번째 줄의 j번째 수는 i와 j가 팀이 되었을 때 능력치이다. 출력 스타트팀과 링크 팀의 능력치의 차이가 최소가 되는 값을 출력한다. 접근 먼저 두 개의 팀으로 나눴다. 스타트팀은 1, 링크팀은 0으로 표시를 한다. 이후 능력치를 조사하는데 2차원 배열을 탐색할 때 행과 열의 인덱스가 모두 1일 때는 스타트 능력치에 더하고 모두 0일 때는 ..

문제 N개의 수로 이루어진 수열이 있다. 수와 수 사이에 N-1개의 연산자를 끼워넣어 최댓값과 최솟값을 구하라 사용할 수 있는 연산자의 수는 주어진다. 입력 첫째 줄에 수의 개수 N(2이상 11이하)이 주어진다. 둘째 줄에 N개의 수가 주어지며 셋째 줄에 + - x / 순으로 개수가 주어진다. 출력 첫째 줄에 최댓값 둘째 줄에 최솟값 접근 수열에서 앞의 숫자를 시작으로 그 다음 수와 연산을 진행한다. 연산자는 사용할 수 있는 개수가 정해져있기 때문에 연산자의 수가 담긴 리스트를 탐색하여 연산자가 남아있다면 그에 해당하는 연산을하도록 한다. 구현 필요한 정보를 입력받으며 최댓값과 최솟값 비교를 위한 수를 설정한다. 중간 결과를 포함한 모든 결과가 -10억 이상 10억 이하이기 때문에 아래와 같이 설정해주었..

www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 접근 뒤에서부터 접근하고자 했다. 아직까지 DP의 개념을 완벽하게 이해하고있지 않아 뒤에서부터 어떻게 메모이제이션을 진행할지 감이 잡히지 않았다. 그래서 다음과 같이 생각하기로 했다. 뒤에서부터 경우의 수에 따라 최댓값을 구하자. 즉 뒤에서부터 진행하면서 해당 날짜에 상담을 했을 때와 안했을 때의 수익 중 최댓값을 채워나간다. 이러한 개념으로 현재 날짜에 상담을 한다면 T일 후에있는 상담을 할 수 있기 때문에 두 개의 수익을 더하고 현재 날짜에 상담을 안한다면 다음 날 상담을 하게되므로 이 두 개의 경우의 수 중 최댓값을 채워나가도록 한다. 구현 ..

문제 N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 같은 수를 여러 번 골라도 된다. 고른 수열은 비내림차순이어야 한다. 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다. 입력 첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8) 둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다. 출력 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증..

문제 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 1부터 N까지 자연수 중에서 M개를 고른 수열 같은 수를 여러 번 골라도 된다. 고른 수열은 비내림차순이어야 한다. 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다. 입력 첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8) 출력 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. 접근 4, 2가 입력될 때 (1, 1), (2, 2) 등도 출력되어야 하기 때문에 DFS로 M개의 수..

문제 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 작성하시오. 입력 첫째 줄에 온라인 저지 회원의 수 N이 주어진다. (1 ≤ N ≤ 100,000) 둘째 줄부터 N개의 줄에는 각 회원의 나이와 이름이 공백으로 구분되어 주어진다. 나이는 1보다 크거나 같으며, 200보다 작거나 같은 정수이고, 이름은 알파벳 대소문자로 이루어져 있고, 길이가 100보다 작거나 같은 문자열이다. 입력은 가입한 순서로 주어진다. 출력 첫째 줄부터 총 N개의 줄에 걸쳐 온라인 저지 회원을 나이 순, 나이가 같으면 가입한 순으로 한 줄에 한 명씩 나이와 이름을 공백으로 구분해 출력한다. 접근..

www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 접근 n에 따라 규칙을 찾고 점화식을 세우려했다. 왜냐하면 크기가 n개일 때는 n-1개에서 특정 크기가 추가되고 n-2개에서도 추가되어 만들어진 것이기 때문이다. 그래서 점화식을 세운다면 f(n) = f(n-1) + 2xf(n-2)가 된다. 구현 n이 최대 1000개가 들어오기 때문에 0으로 초기화된 길이 1000인 리스트를 생성하고 n=1일 때는 1개, n=2일 때는 3개로 설정해두며 for문을 통해 입력된 n개일 때를 구한다. impor..

문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오. 입력 첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다. 출력 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다. 접근 BFS 탐색을 통해 현재위치에서 갈 수 있는 곳을 방문하면서 K..

문제 N!에서 뒤에서부터 봤을 때 0이 아닌 수가 나올 때까지 0의 개수를 구하라. 입력 첫째 줄에 N이 주어진다. (0 ≤ N ≤ 500) 출력 첫째 줄에 구한 0의 개수를 출력한다. 접근 팩토리얼을 구하고 리스트로 변경한 후에 뒤에서부터 0의 개수를 카운트한다. 구현 먼저 반복문을 통해 팩토리얼을 구하여 total에 저장한다. 이후 total을 리스트로 변환하여 각 인덱스에 숫자가 차례대로 위치하도록 한다. 이후 reversed()를 통해 리스트를 뒤집은 후 원소를 꺼내어 0이 나올 때까지 카운트한다. N = int(input()) total = 1 for n in range(1, N+1): total *= n total = list(map(int, str(total))) answer = 0 for ..