https://leetcode.com/problems/add-two-numbers/

이문제 풀다가 간단한 문제고, 문제 풀이도 잘 했는데 뭐가 문제지 했었다. 

결론부터 말하자면 LeetCode에서 코드를 제출할 때 static 변수를 사용하지 말자. 사용하더라도 한번의 코드가 끝나면 static 변수를 초기화해주자

public class Solution{
	static int carry = 0;
    
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    	// carry에 따라 결과값 변화
    }
}

대충 요약하면 이런 상황이었는데,

이상하게 testcase에 해당 wrong answer이 나는 걸 그대로 테스트하면 accept 되는데, 실제로 submit을 해서 넣어 돌리면 wrong answer이 떳다. 이상하게 내 output에 이 올바르지 않은 값이었다.

그래서 엥,, 이상하다 하고 leet code 측에 메일을 보냈었는데, 문뜩 생각이 들어서 확인을 해보니, test case를 1000개를 실행해 주었고, 내가 전역변수로 설정한 carry값이 다음 test case 실행에 영향을 미췄더라면? 이라는 가설을 내고 확인해보았더니 맞았다.

리트코드에서 전역변수를 사용할 때는 꼭 전역변수를 초기화해주자. 초기화하지 않은 전역변수 값이 submition시 test case에 영향을 줄 수 있다.

알고리즘을 역시 안풀어보니까 이런거에도 끙끙 대는구나 싶다... 다시 리트코드 풀러가야지 총총

https://leetcode.com/problems/add-two-numbers/

I was solving this problem and it was a simple one — I thought my solution was correct, so I couldn't figure out what was going wrong. 

Long story short: when submitting code on LeetCode, don't use static variables. If you do use them, make sure to reset the static variables after each run.

public class Solution{
	static int carry = 0;
    
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    	// carry에 따라 결과값 변화
    }
}

To summarize, here's what was going on:

Strangely, when I tested the exact wrong answer test case myself, it would pass just fine. But when I actually submitted the code, it came back as a wrong answer. Somehow my output had this incorrect value.

So I was like, huh, that's weird, and I even sent an email to the LeetCode team. But then it suddenly hit me — I checked and found out that they run around 1,000 test cases, and I hypothesized: what if the carry value I declared as a global variable was carrying over and affecting the next test case? I tested that theory, and sure enough, that was exactly the problem.

When using global variables on LeetCode, always make sure to reset them. Uninitialized global variable values can affect other test cases during submission.

I guess this is what happens when you don't practice algorithms regularly — you end up struggling with stuff like this... Time to get back to grinding LeetCode problems. Off I go~

​​문제를 보자마자 0-1 knapsack 문제랑 비슷한 것 같아 DP. 문제 이겠구나 싶어서
규칙을. 찾으려고 저렇게 끄적였습니다ㅋㅋㅋ

 

처음 저 숫자들의 합만 봤을 때는 뭔가 생각이 반복이 되고 더하기가 반복이 되면서. 뭔가 했는데
전부 다 더한 값을 보니 점화식이 보이더군요

역시 DP 문제는 규칙만 찾으면 코드는 짧은 것 같습니다.

https://www.acmicpc.net/problem/9095

 

9095번: 1, 2, 3 더하기

문제 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다. 출력 각

www.acmicpc.net

근데 진짜로 왜 이런 규칙이 생기는지는 아무리 생각해도 모르겠더군요
​아직 DP 문제 알고리즘은 많이 안풀어봐서 그런지 어려운 것 같습니다
​
그래서 같이 스터디 하시는 분들께 여쭤봤습니다! 그러고 바로 해결!!

 

---

먼저
N이 1, 2, 3인 경우에는 기본 값으로 주어집니다.
변수 n을 표현 할 수 있는 경우의 수를 A(n)라 하면

[기본 값]

A(1) = 1
A(2) = 2
A(3) = 4

[N=4 일 때]

1 + 3을. 표현 할 수 있는 경우의 수 [=A(3)]
2 + 2를 표현 할 수 있는 경우의 수 [=A(2)]
3 + 1을 표현 할 수 있는 경우의 수 [=A(1)]

즉 A(4) = A(3) + A(2) + A(1) = 4 + 2 + 1 = 7입니다.

각각의 경우를 자세히 보면

1 + A(3)	2 + A(2)	3 + A(1)
1 + 3 1 + 1 + 2 1 + 2 + 1 1 + 1+ 1+ 1	2 + 2 2 + 1 + 1	3 + 1

마찬가지로

[N=5 일 때]

1 + 4를. 표현 할 수 있는 경우의 수 [=A(4)]
2 + 3을 표현 할 수 있는 경우의 수 [=A(3)]
3 + 2를 표현 할 수 있는 경우의 수 [=A(2)]

각각의 경우를 자세히 보면

1 + A(4)	2 + A(3)	3 + A(2)
1 + 1 + 3 1 + 1 + 1 + 2 1 + 1 + 2 + 1 1 + 1 + 1+ 1+ 1 1 + 2 + 2 1 + 2 + 1 + 1 1 + 3 + 1	2 + 3 2 + 1 + 2 2 + 2 + 1 2 + 1+ 1+ 1	3 + 2 3 + 1 + 1

이렇게 A(5)가 A(4) + A(3) + A(2) = 7+4+2 = 13 이 됩니다.

---

이전에 만든 수에서 1,2,3을 각각을 더했을 때 현재의 수가 나오므로
1을 더했을 때, 2를 더했을 때, 3을 더했을 때 현재의 수가 나오는. 각각의 이전 조합의 경우의 수를 더하면 됩니다.

만약 이 문제가 1,2,3,4 더하기 였다면
A(n)을 구하기 위해선
1 + A(n-1)
2+ A(n-2)
3 + A(n-3)
4 + A(n-4)
일 때가 A(n)이 나오는 경우의 수일 것입니다.

같은 맥락으로 이 문제가 1,2 더하기 였다면
A(n)을 구하기 위해선
1 + A(n-1)
2+ A(n-2)
일 때가 A(n)이 나오는 경우의 수겠죠?

https://github.com/mjung1798/algorithm_Java

 

mjung1798/algorithm_JAVA

JAVA algorithm study. Contribute to mjung1798/algorithm_JAVA development by creating an account on GitHub.

github.com

 

package com.jyami.baekjoon;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main_9095 {
    public static void main(String args[]) {

        Scanner s = new Scanner(System.in);

        int num = s.nextInt();
        int max = 0;
        List<Integer> list = new ArrayList<>();


        for (int i = 0; i < num; i++) {
            int input = s.nextInt();
            list.add(input);
            if (input > max)
                max = input;
        }

        int dp[] = new int[max + 1];

        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;

        for (int i = 4; i <= max; i++) {
            dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
        }

        for (Integer integer : list) {
            System.out.println(dp[integer]);
        }

    }
}

​​As soon as I saw the problem, it looked similar to the 0-1 knapsack problem, so I figured it must be a DP problem
and started scribbling like that to find the pattern lol

 

At first, when I was just looking at the sums of those numbers, it felt like something was repeating with additions going on, but I couldn't quite figure it out.
Then when I looked at the total sum of everything, the recurrence relation became clear.

As expected, with DP problems, once you find the pattern, the code ends up being pretty short.

https://www.acmicpc.net/problem/9095

 

Problem 9095: Adding 1, 2, 3

Problem: There are a total of 7 ways to represent the integer 4 as a sum of 1, 2, and 3. At least one number must be used in the sum. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 Given an integer n, write a program to find the number of ways to represent n as a sum of 1, 2, and 3. Input: The first line contains the number of test cases T. Each test case consists of a single line with an integer n. n is a positive integer less than 11. Output:

www.acmicpc.net

But honestly, no matter how much I thought about it, I couldn't figure out why this pattern occurs.
​I guess DP problems still feel tough since I haven't solved that many yet.
​
So I asked the people in my study group! And it was solved right away!!

 

---

First,
the cases where N is 1, 2, or 3 are given as base values.
If we let A(n) be the number of ways to represent the variable n:

[Base Values]

A(1) = 1
A(2) = 2
A(3) = 4

[When N=4]

Number of ways to represent 1 + 3 [=A(3)]
Number of ways to represent 2 + 2 [=A(2)]
Number of ways to represent 3 + 1 [=A(1)]

So A(4) = A(3) + A(2) + A(1) = 4 + 2 + 1 = 7.

Looking at each case in detail:

1 + A(3)	2 + A(2)	3 + A(1)
1 + 3 1 + 1 + 2 1 + 2 + 1 1 + 1+ 1+ 1	2 + 2 2 + 1 + 1	3 + 1

Similarly,

[When N=5]

Number of ways to represent 1 + 4 [=A(4)]
Number of ways to represent 2 + 3 [=A(3)]
Number of ways to represent 3 + 2 [=A(2)]

Looking at each case in detail:

1 + A(4)	2 + A(3)	3 + A(2)
1 + 1 + 3 1 + 1 + 1 + 2 1 + 1 + 2 + 1 1 + 1 + 1+ 1+ 1 1 + 2 + 2 1 + 2 + 1 + 1 1 + 3 + 1	2 + 3 2 + 1 + 2 2 + 2 + 1 2 + 1+ 1+ 1	3 + 2 3 + 1 + 1

So A(5) becomes A(4) + A(3) + A(2) = 7+4+2 = 13.

---

Since adding 1, 2, or 3 to a previously formed number gives us the current number,
we just need to add up the number of previous combinations that result in the current number when adding 1, when adding 2, and when adding 3.

If this problem were "Adding 1, 2, 3, 4" instead,
to find A(n), we would need:
1 + A(n-1)
2+ A(n-2)
3 + A(n-3)
4 + A(n-4)
— these would be the cases that produce A(n).

By the same logic, if this problem were "Adding 1, 2",
to find A(n), we would need:
1 + A(n-1)
2+ A(n-2)
— these would be the cases that produce A(n), right?

https://github.com/mjung1798/algorithm_Java

 

mjung1798/algorithm_JAVA

JAVA algorithm study. Contribute to mjung1798/algorithm_JAVA development by creating an account on GitHub.

github.com

 

package com.jyami.baekjoon;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main_9095 {
    public static void main(String args[]) {

        Scanner s = new Scanner(System.in);

        int num = s.nextInt();
        int max = 0;
        List<Integer> list = new ArrayList<>();


        for (int i = 0; i < num; i++) {
            int input = s.nextInt();
            list.add(input);
            if (input > max)
                max = input;
        }

        int dp[] = new int[max + 1];

        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;

        for (int i = 4; i <= max; i++) {
            dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
        }

        for (Integer integer : list) {
            System.out.println(dp[integer]);
        }

    }
}