https://www.acmicpc.net/problem/2230 2230번: 수 고르기 N개의 정수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하시오. 예를 들어 www.acmicpc.net 문제 분석 난이도 골드 5 분류 투포인터 문제 풀이 전형적인 투 포인터 문제, 투 포인터를 사용하기 위해 정렬해준 뒤 앞 포인터와 뒤 포인터의 차이를 이용해 투 포인터를 진행시키면 되는 문제이다. 소스코드 from sys import stdin input=stdin.readline n,m=map(int,input().split()) arr=[int(input()) for i i..
분류 전체보기
https://www.acmicpc.net/problem/5635 5635번: 생일 어떤 반에 있는 학생들의 생일이 주어졌을 때, 가장 나이가 적은 사람과 가장 많은 사람을 구하는 프로그램을 작성하시오. www.acmicpc.net 코드 #include #include #include #include #include #include #include #include #include #include #include #include #include #define LL long long using namespace std; struct Birth { string name; int month; int day; int year; }; Birth arr[100]; bool compare(const Birth& a, ..
문제 링크 문제 링크 문제 풀이 '세 용액' 문제는 '용액' 문제의 심화 문제이다. 용액 문제 링크 '용액' 문제는 두 개의 용액을 선택하여, 두 용액의 값의 합이 0에 가장 가까운 경우의 조합을 구하는 문제이다. '세 용액' 문제를 풀기 전에 '용액' 문제의 풀이를 먼저 한 뒤 '세 용액' 문제의 풀이를 해보겠다. '용액' 문제 풀이 용액을 오름차순으로 정렬하고, 그 중 가장 값이 작은 용액을 A[i]로 칭하고 가장 값이 큰 용액을 A[j]라고 하자. 그 둘의 합이 양수인 경우를 생각해보자. 문제의 최적해는 용액의 합이 0에 가장 가까운 경우의 해이기 때문에 A[i]가 아닌 A[i+k]를 A[j]와 더하면 그 값이 더 커지기 때문에 최적해를 절대 찾을 수 없게 된다. 반대로, 둘의 합이 음수인 경우를 ..
회전 초밥 !https://d2gd6pc034wcta.cloudfront.net/tier/12.svg 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 1 초 512 MB 17881 6251 4435 34.223% 문제 회전 초밥 음식점에는 회전하는 벨트 위에 여러 가지 종류의 초밥이 접시에 담겨 놓여 있고, 손님은 이 중에서 자기가 좋아하는 초밥을 골라서 먹는다. 초밥의 종류를 번호로 표현할 때, 다음 그림은 회전 초밥 음식점의 벨트 상태의 예를 보여주고 있다. 벨트 위에는 같은 종류의 초밥이 둘 이상 있을 수 있다. https://upload.acmicpc.net/f29f0bd9-6114-4543-aa72-797208dc9cdd/-/preview/ 새로 문을 연 회전 초밥 음식점이 불경기로 영업..
https://www.acmicpc.net/problem/1764 1764번: 듣보잡 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. www.acmicpc.net 문제 김진영이 듣도 못한 사람의 명단과, 보도 못한 사람의 명단이 주어질 때, 듣도 보도 못한 사람의 명단을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. 이름은 띄어쓰기 없이 알파벳 소문자로만 이루어지며, ..
https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net N = int(input()) dp = [0, 1 ,2] for i in range(3, N + 1): dp.append(dp[i - 1] + dp[i - 2]) print(dp[N] % 10007)
문제 링크 https://www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 접근 방법 이 문제를 완전 탐색으로 풀려고 한다면 모든 칸을 접근하며 정사각형 형태인지를 판별해야할 것 입니다. 정사각형 형태인지 판별하는 것은 쉽지만 정사각형의 길이가 1 ~ min(n, m)인 경우까지 확인해보아야 하므로 정확한 계산은 어렵지만 못해도 n * m * min(n, m)의 수행 시간을 가질 것이라고 생각되고 이는 최악의 경우에 1초를 넘길 것입니다. 따라서 이전의 정사각형 크기를 기록하여(dp 배열을 이용한 메모이제이션) 현재 위치에서의 최..
문제 https://www.acmicpc.net/problem/14728 Algorithm 전형적인 배낭 문제이다. dp[i][j] : i번째 단원까지 고려했을 때, 총 공부 시간이 j일때 얻을 수 있는 최대 점수 점화식 : dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i].first] + v[i].second - dp[i - 1][j]는 i번째 단원을 선택하지 않는 경우, i번째 단원을 고려하지 않고 이전 단원까지의 최대 점수 - dp[i - 1][j - v[i].first] + v[i].second는 i번째 단원을 공부하기 위해 필요한 시간 v[i].first가 j보다 작거나 같은 경우에만 가능하다. 선택하는 경우에는 해당 단원을 선택하기 전까지의 최대 점수에 현재..
https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 문제 분석 문제 설명 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. 입력 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000) 출력 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다. 소스코드 import java.io.BufferedReader; im..
나중 결과의 출력값으로 대학 이름이 나와야 하므로 처음에 Soongsil, Korea, Hanyang 변수에 입력하도록 하였다. sort 메서드를 사용하기 위해 위의 변수들을 리스트 요소로 대입하였고 univ 리스트의 원래 순서가 필요하진 않은 상황이라 따로 다른 리스트를 등장시키지 않고 sort 메서드를 사용하였다. 문제 조건에서 세 대학의 총점이 100점 이상이면 OK를 출력해야 한다고 했으므로 if 조건에 sum 함수를 이용하여 univ 리스트 요소들의 총합을 구하여 조건문을 작성하였다. 100점 미만일 경우, 최저점을 가진 대학을 찾는 이중 조건문을 밑에 붙였다. sort 메서드를 사용하였으므로 univ[0]이 최저점이고 위에 변수도 같이 할당하여 각각의 대학 이름과 비교하는 코드를 작성하였다.
https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net dp(동적 계획법 - Dynamic Programming)인 문제이다. 처음에 봤을 때는 그리디가 생각이 났지만, 현재 기준으로 높은 숫자가 아닌, 합 중 최대값을 출력해야되므로 dp를 이용하여 풀어야 된다. 양 끝에 있는 숫자들은 더할 수 있는 값들이 정해져있으므로, 제일 왼쪽과 제일 오른쪽의 숫자들은 이전 값들과 누적된 합들을 합해준다. 그리고 중간에 있는 값들은 dp 내에 있는 현재 idx와 이전 idx 값 중 비교하여 큰 값을 불러와서 출력하도록 한다. 그 부분..
문제 https://www.acmicpc.net/problem/14430 14430번: 자원 캐기 인류의 차세대 인공지능 자원 캐기 로봇인 WOOK은 인간 대신 자원을 캐는 로봇이다. WOOK은 언제나 제한된 범위 내에서 자원을 탐색하며, 왼쪽 위 (1, 1)부터 오른쪽 아래 (N, M)까지 자원을 탐색한다. www.acmicpc.net Algorithm 인공지능 WOOK은 오른쪽(r, c+1)과 왼쪽(r+1, c) 방향으로만 움직일 수 있다. 따라서, 현재 위치와 이전에 기록해둔 최댓값을 이용한다. 즉, DP의 Memoization을 활용하여 풀이한다.주의할 점은 인덱싱이다. 가장 윗줄과 왼쪽줄은 먼저 채워주고, 1부터 n까지 기록하도록 한다. Code n,m=map(int,input().split()..
