Problem Solving/BOJ

    [백준, BOJ 1912] 연속합 (java)
    Problem Solving/BOJ

    [백준, BOJ 1912] 연속합 (java)

    출처-https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 내가 푼 방식 : dp[i]에는 arr[i]가 저장되어 있다. 만약 dp[i-1]이 음수라면 dp[i]은 그대로 나두고, dp[i-1]이 양수라면 dp[i]에 dp[i-1]을 더해준다. ==>>처음에 arr[i-1]가 음수면 합이 작아지게 한다고 생각하고 dp[i]에 dp[i-1]를 더하지 않고 그냥 dp[i]=arr[i] 해주었다. 이렇게 하면 음수인 arr[i-1]를 포함하더라도 연속배열을 늘려 d..

    [백준, BOJ 2156] 포도주 시식 (java)
    Problem Solving/BOJ

    [백준, BOJ 2156] 포도주 시식 (java)

    출처-https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 내가 푼 방식 : ('2579번'과 유사) dp[i-3]+arr[i-1]+arr[i]와 dp[i-2]+arr[i] 중에 큰 것을 비교 둘 중 큰 것을 dp[i]에 넣는다. 그리고 dp[i-1]과 dp[i]을 비교. (여기까지는 2579번과 동일) 하지만 계단은 한 번에 3 계단 이상 올라갈 수 없었다. 하지만 포도주 마시는 것은 3칸 이상 건너뛰는 것이 가능하다. 따라서 다음 조건을 추가해줬다..

    [백준, BOJ 9465] 스티커 (java)
    Problem Solving/BOJ

    [백준, BOJ 9465] 스티커 (java)

    출처-https://www.acmicpc.net/problem/9465 9465번: 스티커 문제 상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매했다. 스티커는 그림 (a)와 같이 2행 n열로 배치되어 있다. 상냥이는 스티커를 이용해 책상을 꾸미려고 한다. 상냥이가 구매한 스티 www.acmicpc.net 내가 푼 방식 (윗줄 왼쪽부터 1~5번, 아랫줄 왼쪽부터 6~10번) 그림의 1번에서 출발할 경우 7, 8번으로 밖에 가지 못한다. 물론 2, 6번 외의 모든 곳으로 갈 수 있지만, 7, 8번을 통해서 갈 수 있는 곳들이다. 7, 8번을 통해서 갈 수 있는 곳들은 굳이 저기로 바로 가지 않고 통해서 가는 것이 더 큰 합을 가질 수 있다. 위의 내용을 통해 아래의 결과가 나온다. arr[0][i]..

    [백준, BOJ 11054] 가장 긴 바이토닉 부분 수열 (java)
    Problem Solving/BOJ

    [백준, BOJ 11054] 가장 긴 바이토닉 부분 수열 (java)

    출처-https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 내가 푼 방식 : 이차배열인 dp를 만들고, dp[0]에는 왼쪽에서 오른쪽으로 가는 '가장 긴 증가하는 부분 수열(11053)'을 저장해준다. dp[1]도 마찬가지로 가장 긴 증가하는 부분 수열을 저장해 주는데, 오른쪽에서 왼쪽으로 가는 부분 수열을 저장해 준다. import java.util.Scanner; public class Main { public static void main(String[] args..

    [백준, BOJ 11722] 가장 긴 감소하는 부분 수열 (java)
    Problem Solving/BOJ

    [백준, BOJ 11722] 가장 긴 감소하는 부분 수열 (java)

    출처-https://www.acmicpc.net/problem/11722 11722번: 가장 긴 감소하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} � www.acmicpc.net import java.util.Scanner; public class Main { public static void main(String[] args) { // TODO Auto-generated method stub Scanner scan=new Scanner(System.in); int n=scan.nextIn..

    [백준, BOJ 11055] 가장 큰 증가 부분 수열 (java)
    Problem Solving/BOJ

    [백준, BOJ 11055] 가장 큰 증가 부분 수열 (java)

    출처-https://www.acmicpc.net/problem/11055 11055번: 가장 큰 증가 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수� www.acmicpc.net 내가 푼 방식 : '11053'번과 동일한 방식으로 품. dp 배열에 순서를 저장해주지 않고 합을 저장해줌. import java.util.Scanner; public class Main { public static void main(String[] args) { // TODO Auto-generated method stub Sca..

    [백준, BOJ 11053] 가장 긴 증가하는 부분 수열 (java)
    Problem Solving/BOJ

    [백준, BOJ 11053] 가장 긴 증가하는 부분 수열 (java)

    출처-https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net import java.util.Scanner; public class Main { public static void main(String[] args) { // TODO Auto-generated method stub Scanner scan=new Scanner(System.in); int n=scan.nextIn..

    [백준, BOJ 2193] 이친수 (java)
    Problem Solving/BOJ

    [백준, BOJ 2193] 이친수 (java)

    출처-https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 내가 푼 방식 : dp[i][0]는 dp[i-1][0], dp[i-1][1] 두 경우일 때 다 올 수 있다. dp[i][1]는 dp[i-1][0]일 때만 올 수 있다. import java.util.Scanner; public class Main { public static void main(String[] args) { // TODO Auto-generated method stu..

    [백준, BOJ 11057] 오르막 수 (java)
    Problem Solving/BOJ

    [백준, BOJ 11057] 오르막 수 (java)

    출처-https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수� www.acmicpc.net 내가 푼 방식 : dp[i][j]는 dp[i-1][j]부터 dp[i-1][10]까지 올 수 있다. import java.util.Scanner; public class Main { public static void main(String[] args) { // TODO Auto-generated method stub Scanner scan=new Scann..

    [백준, BOJ 10844] 쉬운 계단 수 (java)
    Problem Solving/BOJ

    [백준, BOJ 10844] 쉬운 계단 수 (java)

    출처-https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 내가 푼 방식 : dp[i][0]는 dp[i-1][1]일 경우에만 올 수 있다. dp[i][j=1]~dp[i][j=8]은 각각 dp[i-1][j-1]와 dp[i-1][j+1]인 경우에 올 수 있다. dp[i][9]는 dp[i-1][8]일 경우에만 올 수 있다. import java.util.Scanner; public class Main { public static void main(String[] args) { // TODO Auto-generated method stub Scanner scan=new ..

티스토리툴바