소프티어

자바코드 정답입니다.

import java.io.*; import java.util.*; 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()); int[][] tree = new int[n][n]; for(int i = 0; i<n; i++){ StringTokenizer st = new StringTokenizer(br.readLine()); for(int j = 0; j<n; j++){ tree[i][j] = Integer.p...

DP로 풀이하였는데 테케 12번에 대하여 반례가 궁금합니다

import sys n = int(input()) field = [list(map(int, input().split())) for _ in range(n)] dp = [[[0, 0] for _ in range(n)] for _ in range(n)] dp[0][0] = [field[0][0]*2, field[0][0]] for i in range(n):     for j in range(n):         candits = []         for dx, dy in [(-1, 0), (0, -1)]:             bx, by = i+dx, j+dy             if bx < 0 or bx >= n or by < 0 or by >= n:                 continue             if dp[bx][by][1] < field[i][j]:                 tsum_value, tma...

BFS로 풀면

BFS로 풀어도 시간초과가 걸리지 않는 문제 아닌가요? 테스트 케이스 전체중에 50프로 문제가 1.1초에서 시간초과라고 걸리는데 이유를 모르겠습니다. #include<iostream> #include<algorithm> #include<queue> using namespace std; int N; int arr[1001][1001]; void bfs(int x, int y){ queue<pair<pair<int,int>,pair<long long,int>>> q; int mv[2][2] = {{0,1}, {1,0}}; int ma=0; q.push({{x,y}, {arr[x][y],0}}); q.push({{x,y}, {arr[x][y]*2,1}}); while(!q.empty()) { int st_x = q.front().first.first; int st_y = q.front().first.second; int check = q.front().second.second; in...

DP로 푼 코드 + 해설 공유합니다 (파이썬)

다른 분들의 연습문제 톡을 구경하던 도중 DP이지만 저와 다른 방식으로 해결하신 분의 풀이 방법을 보고 배워 가는 내용이 많아서 제가 푼 방법도 공유해 봅니다! 문제를 처음 접했을 때는 2차원 DP 배열을 만들어서 dp[i][j][0]에는 (i, j)번째 칸까지의 최대 수확량을, dp[i][j][1]에는 (i, j)번째 칸까지 수로를 넣은 경로 중 가장 큰 값을 집어넣으려고 했습니다. 하지만 스프링클러를 사용하기 전 수확량이 최대인 경로라고 하더라도, 스프링클러를 사용한 후 수확량이 최대가 아닌 경우가 발생합니다. 예를 들어 4 1 3 5 7 9 1 1 1 1 1 1 1 로 입력값이 주어진 경우, 스프링클러를 사용하지 않았을 때 최대 수확량은 (1+3+5+7+1+1) = 18입니다. 그러나 스프링클러를 사용했을 때 최대 수확량은 (1+18+1+1+1+1) = 23이 됩니다. 따라서 이 방식으로 dp배열을 관리하면 오답을 받습니다. 제가 푼 방식은 2차원 DP 배열을 만들고, d...

12번 반례는 여전히 모르지만 푼 방법 공유,,,

2일 동안 dp 방식으로 머리 싸매면서 풀었는데 어떻게 해도 안되길래 뭔가 위쪽 방향에서 합쳐지는 값이랑 왼쪽 방향에서 합쳐지는 값이 같을 때 각 경로 내 최댓값이 다름에도 값을 1개만 저장해주는 게 문젠가 싶어서 dp 말고 bfs로 풀었고 통과했습니다,, 대충 bfs 로 푼 방법 공유 해당 지점까지의 수확량 중 최댓값을 저장할 2차원 배열을 하나 만들고 (이 때 스프링쿨러로 증가된 수확량은 더하지 x) queue에서 뽑은 현재 지점까지의 수확량이 1번에서 만든 2차원 배열에 저장된 지점값보다 작다면 해당 경로는 드롭 오른쪽이나 아래로 뻗은 경로에서 갱신된 수확량이 마찬가지로 1번 배열에 저장된 지점값보다 작으면 해당 경로는 드롭하고 같거나 크면 queue에 넣어주고 1번 배열을 업데이트. 이때 경로의 수확량에는 경로 내 최댓값을 더하지 않고 따로 queue에 넣어줌. N-1,N-1 에선 경로 수확량+경로 내 최댓값 계산해서 정답 계속 업데이트해주기 너무 졸린 상태로 써서 말이...

12번 테케만 틀리는데 반례가 있을까요...?

import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main {     static int[][] map;     static int[][] maxValue;     public static void main(String[] args) throws Exception {         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         int n = Integer.parseInt(br.readLine());         map = new int[n + 1][n + 1];         maxValue = new int[n + 1][n + 1];         StringTokenizer st;      ...

DP로 푼 코드인데 12번 테케만 틀립니다 도와주세요 ,,,

import java.io.*; import java.util.*; public class Main {   static int n, ans;   static int[][] map;   static long[][][] dp;  //마지막에 값이랑, 쿨러포인트   static final int[] dr = {1, 0};   static final int[] dc = {0, 1};       public static void main(String[] args) throws IOException {     BufferedReader br = new BufferedReader(new InputStreamReader(System.in));     StringTokenizer st;     n = Integer.parseInt(br.readLine());     map = new int[n+1][n+...